Es muy fácil: te vas a Ajustes > Administrador de aplicaciones y en TODAS seleccionas Galería. Ahí le das al botón de "borrar datos" y "borrar caché".
Pero antes de eso vete a Ajustes > Cuentas y sincronización, y si tienes activada la sincronización automática tendrás que deshabilitar la sincronización con Picasa, o de lo contrario te volverán a aparecer otra vez.