Thanks for the replies!
I don't think there is any particular right or wrong with these systems.
As a general opinion though, I think that global (including static) state is to be avoided; it's not thread-safe and pretty much assumes/requires that you only have one instance of the system overall. Generally it's not a good idea to solve problems by reaching for global state out of the programmer's toolbox without a good reason.
I would move the management of all states more towards your "currentState" pointer and whatever it is that owns that pointer: "the state manager/machine", in your case it's main.cpp.
In fact you can kind of simplify things, what you've implementing with two vectors and a few loops is basically a map. So just use a map!
Each state has a local (non-static!) member, which is a map that maps the key to the subsequent state:
std::map<char, State*> keysToStates;
Then you just use the map to lookup the state based on the input key.
I wrote a similar system recently for a game. It was similar to yours in a few ways, but different also. Described thusly:
Each state had a render() function which was my (graphical) equivalent to your giveOutput() function.
There was also a process() function which returns a State pointer; this is the pointer to the next state. So my process() function acts as a combination of your nextState() and getInput() functions. You could even make the return optional (using boost::optional, or by returning null if you use raw pointers) and then the absence of a returned state can be interpreted as a quit, so it could also subsume your quit function.
My process() function was responsible for gathering input (like your getInput) and doing the main 'thinking' that the state needs to do.
Another difference between my states and yours is the way that states are driven to transition. Your transitions are based on key inputs - there is absolutely nothing wrong with this so long as state transitions are _always_ driven by key inputs. That's a decision you need to make. This was not the case for me however, for example a gameover state is reached when the player loses all their health, in this case clearly it is not based on an input key but on some internal game logic. Therefore I couldn't just directly map key inputs to the state transitions.
To achieve this I wire states together a little differently. Each state knows about the states that it can transition to in an abstract way. For example the main gameplay state knows that when the main character dies it needs to move to a gameover state. So it has a member function on it, something like this: setGameoverState(State * gameover);
Now, the transition occurs when the process() function decides the transition should take place. It could be looking at the key input (in which case it works similarly to your system), or in this case it is looking at the remaining health and once it hits zero it returns the gameover state from the process() function.
Note however that the main gameplay state doesn't *really* know anything about the game-over state. It simply knows that some kind of gameover state exists, but it doesn't care what that actually is. So states are still isolated. You might wire in a GameoverScreenState or HighscoresScreenState, or a DeathSceneState, whatever you like.
Perhaps, generally speaking, states would be driven by input, in my system I might create a convenient AbstractKeyDrivenState, which holds the map of keys-to-states that was discussed above.
One final point. My states also have abstract functions for entering and leaving a state. If the nextState != currentState then these functions would be called. They allow the states to setup/init and de-init themselves (releasing resources, etc). For example when entering (or re-entering) the main gameplay state it has to (re)setup the world, load all the resources, etc and unload them all at the end as well. The enter() function was actually an enter(State*) function, where the previous state was passed into the next state. This allowed states to implement a backup feature where they can return you back to the last state you came from without having to explicitly wire them up beforehand (and explicitly wiring them wouldn't work if a state can be entered from multiple other states as you wouldn't know which state was the correct one return to).