Rook's Rest is a coastal town in the Crownlands which answers directly to the King on the Iron Throne. It is located north and east of King's Landing on the north coast of Blackwater Bay, east of Duskendale but west of Crackclaw Point.
When Davos Seaworth helps Gendry escape from Dragonstone island so Melisandre cannot burn him alive as a human sacrifice, he provides him with a small rowing boat and directions. Davos instructs Gendry to follow a certain star in a straight line, which will allow him to travel due west through open water - instead of just rowing to the closest shore at Crackclaw Point, as this would be his most obvious path of escape. Davos explains that after rowing due west for a full day and night, he will reach Rook's Rest. Davos says he will want to stop at there, but he should continue on as Melisandre would find him there. Davos tells Gendry to instead follow the line of the coast west after Rook's Rest, and he will eventually make his way back to King's Landing.
In the books
In the A Song of Ice and Fire novels, Rook's Rest is the seat of House Staunton. The map in the fourth novel, A Feast for Crows, misspells the name as "Rooks Rest".