GPS being a US military system produces coordinates that Google maps and Google earth use natively. The coordinates use a World Wide Datum called WGS-84 i.e. World Geodetic System 84.

Most GPS's will output NMEA 0183 sentences on their communications port which also use the same WGS-84 datum.

The world is basically a flat ellipsoid shape and paper maps are flat and the easy to use flat paper maps will use a grid system (Cartesian coordinates) such as the Ordnance Survey Maps in the UK or the Military Grid Reference system MGRS etc

http://www.ordnancesurvey.co.uk/oswebsite/gi/nationalgrid/nationalgrid.pdf

The calculations to turn native GPS output i.e. using the WGS-84 datum into a flat grid reference can be a little difficult by hand.

http://www.movable-type.co.uk/scripts/latlong-convert-coords.html

i.e. The computer program on the cellular phone will convert between the native GPS and the Grid coordinate systems)

Lat (WGS84) N56:40:30 (56.675060)
Lon (WGS84) W3:00:13 (-3.003490)

becomes

OS Grid NO386541 (this is so much easier to locate on a OS 1/25000 and 1/50,000 scale paper map grid)

Distance between OS grid coordinates simply become basic Pythagoras for example.

The paper map you use will have a specific datum (written somewhere on the map). When using a commercial GPS you need to ensure that the GPS also is using the same datum as the paper map and not WGS-84 or you may get some significant navigational errors.

Hope this helps.