Per prima cosa, utilizza mod_rewrite o soluzione equivalente per far si che per tutti i vecchi URL venga effatturato un redirect 301 verso i nuovi URL.

Poi attiva il Google Webmaster Tools e controlla il passaggio dello spider e le altre statistiche.

Infine, ripassa regolarmente gli errori 404 per verificare la presenza di ulteriori vecchi link in entrata ed aggiungi anche questi al primo punto.