I'm looking at the Nikon AF 70-300/4.0-5.6 G Black Nikkor Lens, and that page says that it's not compatible with Nikon D40, D40x, D60 and D5000. I'm not sure - would it work with my D80?
Your D80 is compatible with all Nikkor lenses produced since 1977. It has a Nikon F-mount and this is compatible to some degree with all lenses utilizing the Nikon F-mount, produced since 1959. Lenses (of various manufacturers, not just Nikon) produced prior to 1977 can still be used after modifications. As long as Nikon does not pursue a new mount, all future Nikon lenses will also be compatible with your camera.