A little overview to the devices, apps and things used for navigation after 3 years of cycling in north and south america. They are each a little different and have their advantages and drawbacks.

Paper Maps

There may be places where they are the only way to go but I feel that they are outdated, especially for a normal bike tour (unless you really want to stay away from electronics). The best part is being able to see all roads that they have without having to zoom in like you do on google maps, etc. There are trails where paper maps are amazing (e.x Canol Trail, backcountry hiking and backroad maps in British Columbia) and others where just carrying the topo map on your device is much better (e.x. 200+ printed pages for CDT or a digital version).

Garmin Etrex20 / GPS unit

garmin maps is like a box of chocolates, you never know what you're gonna get

While I am no expert in those and garmin basecamp remains one of the biggest mysteries of life, here is my opinion on this. The pros are that you can keep it on all day, see it well in sunlight and follow/record a track with very low battery use. In places where you can get good maps, topo maps and tracks to follow it is invaluable. (e.x. following a gps track for GDMBR, Trans Ecuador, Baja Divide and many other routes and hikes). It is also a big plus to use it alongside a phone so that you always have two GPS enabled devices and if something goes wrong you can find the way out. Amazing to navigate in cities that you don't know.

Cons: For the etrex20 unit, is pretty much using the non-reusable batteries, although I finally found a USB-rechargeable pair that will come in handy. Topo maps are normally very expensive and difficult to come by but you can use a website such as the Netherlands OSM to select and download free OSM maps for your unit (no topo, nothing too fancy).

map sources:

http://garmin.openstreetmap.nl/ - select the squares, countries, continents you want and request the dowload. Absolutely necessary to have at least those on your GPS unit, otherwise you are only limited to following gps tracks or recording your own.
http://www.gpsfiledepot.com/maps/state/all - maps for USA, I have not used it but its there
http://www.ibycus.com/ibycustopo/ - (CANADA) I can personally vouch for this one and I love it. Free topo map for all of canada. Download is either by buying a dvd or lookingup the torrent (search for ibycus maps on any of the torrent sites and use a downloader to get the image).
garmin maps (cd's or digital download) - I was passed forward one for Mexico and really liked it. Good detail, lots of fun-nonexistent roads. They seem to have plenty of maps covering a lot of different countries but they are not cheap. Not practical to buy them for an around the world ride but for an area you frequent or live at, it would be a good investment
pick your own adventure via gpsvisualizer - make a route in google maps and export the link to gpsvisualizer to create a .gpx file which you can load on the garmin. Or draw a route by hand on Google Earth (especially useful with the sat view and if area has no maps!!!). Very handy but both of these require a laptop or being at a desktop computer in a cyber cafe (these are more common in some parts of the world than others).

Google Maps

Very useful to download maps for offline, especially if you are not sure where you are going and want to look at them later.

Plan B is to load the topo or satellite maps and cache the data by scrolling of where you want to go. This will stay stored on your device and you can look at it but if you restart it or lose power its gone. There are better options, below!

Alpine Quest - the holy grail of all navigating apps (as far as I know, android only)

I don't know where to begin. I got this app suggested by a friend but it took a while to learn all its features and use them properly. The free version is pretty limited but the full version is about 5-6$. Here is what it can do:

Offline: Save Open Street Maps for later (including topographic and various different options), very handy for offline use!
GPS location and GPS tracking. All phones and tablets with a GPS unit will work without service or wifi!!! and they work well, I have not had any issues getting a location outdoors throughout north america and colombia, dubai, oman, morocco, spain, you name it. Different options for the gps logging but having it on is a bit of a battery drain (it also takes longer to locate than a regular gps unit).
Other maps - you can load other maps such as google satellite, google maps and even display a google roads overlay over the open street topo map. That's like getting the best of both worlds!!!

you can save map sets of your chosing (google sat with google roads overlay and OSM topo with google roads overlay is very handy). Red squares option shows which areas you have downloaded/saved (in green).

map caching - although you can't straight up download google maps... if you browse through all the data gets cached and saved to your tablet (or sd card if you chose that option). Saving google satellite for later or OSM topo with roads and google roads overlay is pretty good. Rendering the much slower google maps app useless (save for downloading large areas if not sure where to go).

waypoints and route drawing - ROUTE DRAWING. with google satellite you can browse to seemingly roadless areas and plot your route by making waypoints or drawing a path.

Route display (.gpx, .kml, etc.) - a very handy feature since it bypasses the garmin limitations of 2000 (or more?) points per track. There is nothing like loading up the entire Great Divide Mountain Bike Route in one go in it's entire 14000+ point glory!

CONS:

it would be tough to see on a sunny day
if all you want to do is follow a track, definitely less useful than a garmin gps unit (stopping to take out phone/tablet vs garmin just being out there)
it uses a bit of battery especially if you are logging your route(not a major one but it adds up, better to carry a cache battery or two)
slower gps locate than a garmin (I did see a friends phone pick up the location in seconds w/o service, maybe my 2014 tablet is too old)

NOTE: if using it don't forget to turn Airplane mode ON (you can still use the GPS) otherwise w/o service your phone battery will drop quick.

Conclusion

I am sure there are plenty of ways to navigate but this is what I use and I like it.

Alpine quest really takes the highlight as the go-to navigation at all times but in more remote places the garmin is definitely nice to have as well as when following a gps track. Paper maps shine on short, planned trips or when other alternatives aren't very helpful or when they are just really good (BC backroad maps!)

honorable and not-so-honorable mentions:

maps.me - used to be great for offline navigation but a change was made that split countries and even provinces in multiple parts thus not knowing if you have downloaded the particular section when you need it (e.x. zooming in the backcountry of British Colombia to get an error that you need to download "British Colombia, north-west")

canada topo maps - good topo maps, destroyed my miniSD card as some of the comments said, lets me hanging for a week. Good that I had the garmin there as well.

OSMand - OSM maps, actually very useful since you can download a whole country. Loads slow but downloads are small-ish and its some of a backup map if you venture into an area not saved by alpinequest

Gaia - never used it but heard good things about it (for iphone, Alpine quest alternative?)

Asking locals - well in the end this is your most reliable intel and sometimes your only one. Be ware as many people would say there is no road if they don't know or they don't think you can do it.