BGL is a template library which (I think) means that everything is just a bunch of header files. The Graphviz stuff apparently needs to be compiled though, and while I installed all of the Boost stuff through my package manager (Fedora 12) apparently I did not get this Boost/Graphviz stuff.
Here are the steps I went to build libbgl-viz.so, which can be linked to in order to run the graphviz examples. This is probably all documented somewhere but I could not find very clear instructions anywhere. Also it's worth noting that if you build a dynamic library you will probably have to distribute it with your application as you can't rely on it being in the Boost distribution (because it's not)!
1) Download boost-1.4 source.
2) Go to boost/libs/graph/src.
3) g++ -c *.cpp -I../../../ -Wno-deprecated -fPIC
4) g++ -shared -o libbgl-viz.so *.o
5) Next steps are optional if you do not want to install system-wide.
6) sudo chown root:root libbgl-viz.so
7) sudo mv libbgl-viz.so /usr/lib/
8) Try building some of the examples, you will need to link with boost_graph, libbgl-viz, and boost_regex. If you get any errors try playing with the order.
9) Go party!