If not mistaken it has Nokia Maps, but u can install Garmin if you want, just buy external GPS receiver like Holux and u are ready to go.
for 5800xm, if not mistaken Garmin has not released any version for this particular phone yet because the screensize is relatively big, well u can use s60v3 because 5800xm has backward compatibility. Just that the screen is smaller and at the mean time wait for Garmin to release a new version which support 5800xm completely (5800xm user please correct me if i am wrong).

Please read the first page, I already explain the whole thing, GPS is free for life. Just that the Navigational software is not free. Eg Mapking, Garmin, Nokia Map need to be bought in order to use it to navigate from a place to another. Garmin is more popular due to the constantly updated Malsing and Malfree map.