Ejecutando g++ -v -v -v genera muchas cosas, incluidos todos los directorios de inclusión buscados. vector está en uno de esos.
En mi sistema Debian Estable vector está aquí:
/usr/include/c++/4.4/vector
GCC normalmente tiene los encabezados estándar de C++ instalados en /usr/include/c++/<version>/ . Puedes ejecutar gcc -v para averiguar qué versión tiene instalada.
Al menos en mi versión, no hay vector.h; el encabezado público es solo vector (sin extensión), y la mayor parte de la implementación está en bits/stl_vector.h .
Ese es el caso de mi distribución de Ubuntu; su distribución puede diferir.