I don't really know much about how the US government is structured, but:
1) Categories like these should always be plural. That's how we've been doing it, and how Wikipedia does it, so I'd say that's standard. So [[Category:Senators of Virginia]] (or maybe [[Category:Virginia Senators]]?) and [[Category:US Secretaries of State]].
2) As for subcategorisation, probably [[Category:US Senators]] and [[Category:US Governors]] would be useful. Beyond that, like I said, I'm not really familiar with the system, so I'd leave that up to someone else.