Cambio a URLS Amigables y su posicionamiento

[zeroweb]

Hola! tengo la siguiente duda...
En google tengo indexada muchas paginas del estilo:
SITIO/pagina.php?cat=1&idnoticia=2

y a traves del htacces las transforme para que sea:
SITIO/pagina/categoria-uno/titulo-dos

Donde "categoria-uno" es el titulo de la categoria id=1
y "titulo-dos" es el titulo de la noticia de id=2

Y tengo otra pagina:
SITIO/paginaUNO.php?variable=1

Y la transforme a:
[B]SITIO/pagina/variable-uno

Mi pregunta es como le tengo que avisar a Google (u otro buscador) del cambio de mis URLS?

Solo con mandar el nuevo Sitemaps google indexa las nuevas URLs y desindexa las viejas que ya no sirven?

Se que durante un tiempo deberia dejar ambas URLS por si los visitantes entran a la vieja.. pero cuanto tiempo mas o menos?

Tengo miedo que este cambio afecte negativamente a mi sitio.. en ves de positivamente que es lo que busco :P

Otra pregunta... como veran hay dos paginas diferentes "pagina.php" y "paginaUNO.php" que luego se transforman en SITIO/pagina/...

Esto es correcto? Que dos paginas diferentes apunten a la misma variable "/pagina/"??

Bueno espero que me hayan entendido...Saludos y gracias!