How to deal with this kind of node references, when creating a new instance of a content type?
I would create a taxonomy hierarchy that has nested State -> Cities. You can then provide a way for them to choose a state, and filter a drop-down by the parent taxonomy. 

Hierarchical Select will do this for you.

If you need to create a content type for city, just apply the same taxonomy term to link the two together.

Kim