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?
Yes it will work. Those cameras don't feature an in body focus motor and won't autofocus with any "AF" lens. Your D80 should be fine with any AF or newer AF-S lens.
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.