alt Hacker NewsYes, they should be discoverable. There are platform conventions for this: on Windows you'll see underlined letters; menus show you the shortcuts. Tab is a pretty much universal "move to next field" shortcut and I don't think that's particularly discoverable if you don't already know it.
There's nothing wrong with a keyboard driven UI having buttons as long as they advertise their key, though. That's one way discoverability is supposed to work. It means you can fall back to the mouse when it makes sense.
Since you mentioned Windows, Microsoft made Ribbon which uses Vimperator-style navigation to make toolbars and buttons discoverable as long as you know one hotkey (Alt). It can also be hidden until triggered with a hotkey. This is miles ahead of most discoverability tricks in power user interfaces, including fuzzy command search which is not guaranteed to remain stable as new commands are added.