It is a message seemingly carved into the floor.
Next to the Pokemon center go up the stairs to the platform, there will be a lady there that gives you U-Turn.
if you stand inbetween the two benches to the right of her, take one step south, one step east, and then turn around, you'll find a written message seemingly carved into the floor. It's not a hidden item, so it wont get picked up by the dowsing machine.
The message is pretty interesting. It doesn't say if this is the actual gift but most people are convinced it is, since it's more special than getting an item.
Sources: Walkthrough and Gamefaqs
Hope I helped.