Allora... secondo me stai facendo un po' di confusione

Url Routing non è un qualcosa che, sottobanco, sostituisce l'URL visualizzato sul browser, ma agisce in maniera differente: tu digiti nel browser "www.miosito.com/categorie/navi-da-crociera"; il server invoca l'httpHandler che hai creato ed esegue la pagina ShowCategoria.Aspx passando l'input "navi-da-crociera"
Una volta compreso questo, penso che le tue domande si rispondano da sole. Un'ultima cosa... ovviamente per supportare "navi-da-crociera" come chiave di ricerca, è necessario che la tua categoria abbia un campo contenente questo dato, che magari autogeneri in fase di creazione.
Ciao,
m.