No, you don't need any internet connection for the navigation. With StreetDeck, specifically, the map data is included on the installation DVD. The top-end version of Centrafuse (when released) will include map data, as well.
Other frontends dont' include map data, and forum members have tken great lengths to integrate them into the front ends, with varying levels of success.
I'd check out the subforums for Roadrunner, FrodoPlayer, Centrafuse, Freeway, etc. to see the options you have for navigation.