Starting at the top: it is NOT a good idea to specialize the adjacency list and add you own methods to it.
Instead you should create an instance of the boost::adjacency_list class as a member of a new class that you can then write methods for.
class cNavGraph {
public:
boost::adjacency_list < boost::vecS,
boost::vecS,
boost::undirectedS,
NodeInfo, EdgeInfo > myNavGraph;
...
Now, to retrieve vertices from the graph by the vertex property nodeIndex you have two options:
Search the vertices for the nodeIndex you want. This is simple but will be slow if the graph is very large.
Create a map from nodeIndex to vertex as you add the vertices, then do a lookup on the map when you need to get the vertex from the nodeIndex. This needs more code and memory, but will be much faster for large graphs.
As a more radical sugestion, I propose redesigning things so that you make the NodeIndex and the vertex descriptor identical, like this
for (std::vector<EdgeInfo>::const_iterator it = edges.begin() ;
it != edges.end(); ++it)
{
add_edge( it->first_node_index,
it->second_node_index,
myGraph );
Note, in reply to your comment, that the call to add_edge will automatically add the two vertices, if they are not already present, with vertex descriptors equal to the node indices specified. Do not call add_vertex!
When you have completed adding all the edges, you can iterate the through the nodes, adding the properties ( as many as you want ).