they were in Casterly Rock, besieged by the Greyjoy fleet.
Casterly Rock is on the mainland of Westeros, not an island. A fleet couldn't keep them in Casterly Rock. It could only keep them from sailing away. The fleet burned their ships. At that point, they could only leave by land.
At roughly the same time, the Lannisters were besieging Highgarden. Highgarden and Casterly Rock are both about the same distance from King's Landing by land. And of course, there is always a road to the capital from any major castle or city. Casterly Rock is mostly north of Highgarden and a bit to the north of King's Landing. Highgarden is a little farther south of King's Landing but not as far west. The point being that it is unsurprising that the Unsullied could reach King's Landing almost as quickly as the Lannister army.
The Unsullied simply had to do the same thing that Jaime's army did. Travel by land across the width of the mainland. This presumably required a month of travel. They didn't depict practically any of the travel this season, which has made it difficult to keep track of time. As far as we know, Highgarden and King's Landing are practically next to each other, while Casterly Rock could be farther away. But in reality, both are a long way from King's Landing.