Marble will support offline routing (calculating routes without Internet access) starting with KDE 4.6. You can use subversion trunk to give it a try already. This page lists installation steps necessary to install experimental Marble packages and Gosmore, an offline router, on a Nokia N900 device.
The Marble version you are going to install is experimental and not well tested. The installation is not intended for casual users. SSH access to your N900 is required.
echo "deb http://nienhueser.de/marble/maemo binary/" > /etc/apt/sources.list.d/nienhueser.list
From there on you can use Maemo's package manager to install Marble and Gosmore: Open the package manager, refresh the package list and install Marble and Gosmore from the navigation section. Now start Marble from the application menu to make sure the installation went fine.
Given the limited computing power of the N900, I'd strongly recommend to do the required map conversion (OSM .xml format to gosmore .pak format) on a different system with more power. You just need to ensure that the .pak file generated is compatible. Version 20090624-1 and older for example are not compatible. Please consult the OSM Wiki for more details on installing gosmore.
You need some part of the world in OSM .xml format. The best way is to download one of the ready snapshots listed in the OSM Wiki. Don't choose the entire planet, but a reasonable sized map. A 132 MB .osm.bz2 works fine here for example.
Assuming you downloaded a OSM .xml map called mycountry.osm.bz2, create the .pak map for Gosmore like this:
bzcat mycountry.osm.bz2 | gosmore rebuild
Depending on the size of the map and the speed of your computer, the map generation will take between a couple of minutes and some hours. Once done, gosmore itself opens the map in a new window you can close. The map file you are looking for is gosmore.pak.
First, create the directory on your N900 where Marble will look for your Gosmore map.
mkdir -p /home/user/MyDocs/.local/share/marble/maps/earth/gosmore/
Afterwards copy the previously generated gosmore.pak to the N900:
scp gosmore.pak root@IP-of-your-n900:/home/user/MyDocs/.local/share/marble/maps/earth/gosmore/
When following the instructions above, Marble will automatically include Gosmore to calculate routes. In offline mode, Gosmore will be the only routing provider used. It looks similar to this: