Lambertus did a similar service yournavigation, which basically it works like this (Lots of things might be different):

  1. web client ask for a route betwwen pos1 and pos2
  2. a server side php script parses
  3. php script invokes gosmore to route between pos1 and pos2
  4. gosmore will choose the ways that are best suited
  5. gosmore will then gather all the nodes that you need to travel through
  6. these will be outputed to the PHP script which converts them for web consumation.
  7. the web client gets these nodes and then draws them with standard openlayers.

The most important part for you is, “gosmore”, it’s an application that will take the openstreetmap data and create a custom database from it which it later uses for creatingroutes. It’s done like this:

  1. download and configure gosmore
  2. download planet.osm
  3. parse planet.osm output database
  4. run gosmore with database.