Very simply. It's as trivial as you can imagine.

You prefetch the list of locations in the area of interest (there won't be that many compared to the humongous amounts of space Google apps consume already), you keep your user's "personality matrix" synchronized, and then when user asks, e.g., for a restaurant nearby, you display them from off-line cache, sorted by distance, characteristics and by how well they match user's personality matrix.

It would be that simple, if it was about actually suggesting places. But it isn't. It's about suggesting places that pay for advertising and successfully billing them, while also collecting as much data about the users as possible. It's a common occurrence on mobile (and also increasingly common in hardware and desktop software) - things that don't need to be on-line are put on the Internet nevertheless, to facilitate a specific business model.

Someone once told me that this is how Apple Maps works so that they can maintain a high privacy standard - though I'd be curious if someone else could verify.

Maybe, for starters, by querying the area of the map that is currently displayed, rather than your current location? Which is more in line with what you'd usually want anyway.

On my Window phone, I have an app that can do navigation while offline... many companies, like Google, want everything to be server side because they want to learn more about you.