I use conkeror--which is a vimperator "clone" based on xulrunner, with emacs-like keybindings and commands.
"Is it problematic when a site has graphics for navigation?"
It depends. Most of the time it's still a link, so the browser has no problem identifying and highlighting it as such. If it's something fancy (image map? JS magic?)--it can be a problem. Fortunately, such sites are not common.
"Do you cycle through links and then choose the one you wanted, or is there a more direct way of accessing them?"
You press 'f' (for "follow") and a number appears next to each link. Then you enter a number to follow a link.
"Is it really faster than using a mouse?"
It depends. For example, there are whole WM environments which are designed to work without mouse (ratpoison, stumpwm, xmonad, etc.). Naturally, a keyboard-driven browser lends itself beautifully to such environments. Other than that, I find it annoying having to move my hand from the keyboard each time I need to look something up with a browser.
Of course, when I just surf the web, the mouse is usually more convenient.
"Do you need two hands to be efficient, and if so, wouldn't you rather be efficient with only one hand, for example using Opera's mouse gestures?"
Since conkeror is modeled after emacs, I'd say yes (unless you happen to be using a custom keyboard layout or something). As for the efficiency--again, it probably depends on the "mode" I am in (mouse is easier for plain surfing).