Google Maps' offline feature is a bit misleading. You can't search or get directions without an internet connection. Although, if you are already navigating and the connection drops and you have the maps offline it would continue to navigate you.
However, your starred items do remain even while offline. So for travelling without data, given some planning time, you can star a bunch of stuff while you have wifi, and then navigate using the offline map without search.
I've tried many other solutions, and this really was the simplest and best for me.
