Effectivement, le sitemap peut aider à faire indexer les pages profondes de votre site.
Créer aussi un plan de votre site (en html par exemple) avec un lien dans votre footer est également un moyen de faire connaître les différentes pages aux moteurs de recherches.
De plus, il ne faut pas oublier le maillage interne de vos pages qui permettra d'améliorer l'indexation de ces dernières.
Pour moi c'est de la connerie un sitemap. J'en ai jamais fait un seul et pourtant mes sites sont très bien référencés. Comme le dis Cylo, il faut aussi réflechir à son maillage interne dès la création du site