Google sí indexa URL's con parámetros, pero tiene un límite, aunque de cualquier forma una URL sin tanto parámetro siempre luce mejor y ya habrás escuchado el viejo dicho que reza: "Lo mejor para Google, es lo que sea mejor para los usuarios" (quién sabe qué tan cierto sea, jeje).
Muchas personas llaman a lo que tú quieres hacer como
URLs Amigables, quizá de esa forma también puedas encontrar información.
Básicamente lo que necesitas es un manejo medio de
expresiones regulares.
En el foro se ha hablado ya algo de eso,
mira por ejemplo aquí.
El sitio oficial también habla sobre el tema
Apache module mod_rewrite, aunque no se me hizo muy claro la primera vez que lo vi.