And therefore you can't say they're different things, because their identity IS their statehood...or someone having taken that statehood away. Or having regained it - usually by their own efforts.
Well, "statehood" is normally a rather inflexible and even juridical term, denoting quite simply the possession of citizenship in the state in question. In my opinion it is obvious that this is not neccessarily connected with national identity in the sense discussed here, which may tend to be a bit obscured by the widespread use of the word "nationality" in the sense of "possesses citizenship in".
Also, I think Sid has a very obvious point when he observes that nationality is essentially a state of mind. But it depends somewhat on the circumstances. Broadly, people fall into one of three categories:
1) People whose families sare solely or overwhelmingly from the same ethnic and cultural background, and who lives in a place where this ethnic group clearly dominates
2) People whose families come from a significantly mixed background and who live in a place where there are several ethnic and cultiural groups of comparable size and influence
3) People whose families are solely or overwhelmingly from the same ethnic and cultural background, but who lives in a place where this ethnic group is a realtively small minority
In the case of Group 1, the question of national identity will normally be self-evident. Norwegians or Icelanders living in Norway or Iceland would be examples, as would a German whose whole family has lived in Berlin for 3 generations. In other words - their family background and residence offers a more or less automatic identity, and alternatives can only be found at the point of absurdity - either by assuming a nationality to which it is obvious that the person has no real claim (such as Olafur Olafsson, from a long line of Reykjavik fishermen, deciding that he is French while continuing to live on Iceland), or by inventing a new national identity based on regionality that will in practice be difficult to sustain because it is ultimately futile to consider yourself as belonging to something that virtually nobody belives exists (such as Dieter Müller from Berlin insisting on considering himself a Prussian and not a German). For people who fall into this group, nationality will only be an issue to the extent that that the national identity that he is more or less automatically offered is in itself problematical. Belgians is a case in point - if you are clearly of Flemish descent, you can with comparable credibility consider yourself Belgian or Flemish, or for that matter you can consider yourself both, and regard them as complementary identities.
Major point: That nationality is a state of mind doesn't mean that everyone can choose whatever nationality they want. We are offered a limited choice, defined largely by circumstances beyond our control. In order to credibly claim a given nationality a person must fulfil certain criteria, normally connected with language, descent and residence, if not neccessarily all of them. In many, perhaps most, cases the issue of national identity is more or less self-evident.
However, if Group 1 chiefly demonstrates the limitations in the concept of nationality as a chosen indentity without falsifying it, then Group 2 illustrates the indispensability of the concept. Into this group would fall, for example, a German speaker of mixed descent living in Czechoslovakia, or a Russian speaking Latvian citizen with one latvian and one russian parent. They each of them have two clear options available to them. The two are Czech and Latvian by statehood and residence, but German and Russian by language - and mixed by descent. There is no viable objective grounds in either of these cases for placing any of these people into one national group or the other - they will be what they choose to be. A characteristic that sets them apart from Group 1 (f.e. the Belgians) is that they have no "third option". "Belgian" can be regarded as a national identity that supersedes "Flemish" and "Walloon" without contradicting either of them. "Czechoslovak" or "Latvian" doesn't. As with so many things in this field, there is no strictly logical reason for it, just that nobody thinks of f.e. "Latvian" as a nationality that encompasses both ethnic latvians and ethnic russians living in Latvia, at least not yet. With a sufficiently long time perspective, there will even be a choice for people who don't come of mixed descent if they live in a place that offers several possible identities. For example, two or three hundred years ago in Central Europe, nationality was largely a linguistic issue and decided largely on social grounds. If you lived in Prague and was a merchant, you spoke German. In most cases your family would then still be speaking German in 1930, but it may have been as Czech as 2 beers for lunch when the nationality shift took place.
Now, the authorities can (and do) sometimes apply criteria that links nationality to statehood, such as when Czechoslovakia defined everyone with German as their mother tongue as Germans, deprived them of statehood and expelled them after the war. That however concerns their legal status as citizens of the state. It is more than questionable in my opinion if such a judgment really constitutes a valid definition of nationality. But it does go to show that it is possible for the questions of statehood and national identity to overlap and even to clash, which illustrates another basic point: While national identity is essentially distinct from statehood (and from "nationality" in the technical sense of citizenship), they are not neccessarily unconnected. Again, it all depends on circumstances.
Group 3 raises another set of issues, namely a majority identity versus a minority identity. That can be due to immigration, or to a long established ethnic pattern at the place of residence. The son of an Indian immigrant family in London has both Indian and British available to him as possible identities. A Catalan can regard himself as either Catalonian or Spanish in their nationality. They differ from from Group 2 mainly in that the choice has some different connotations. In the former case, a clear choice of nationality implies either cutting yourself off from your family and cultural roots, or defining yourself as essentially a stranger in the place you have lived all of your life. In the latter case, a clear choice implies either aligning yourself with a minority cultural identity (which may be, according to taste and circumstance, either a source of fierce pride or an object of shame) or with a majority one. It is perhaps not surprising that by far the most usual choice is to accept the uneasy compromise of seeing oneself as belonging to both.
Basic conclusion: To the extent that an individual has more than one option open to him in the question of national identity, there is essentially no other basis than the choice of that individual. And there is almost always more than just two, clear-cut options. In short - national identity is impacted by circumstance, but essentially as flexible and as much a question of choice as any other type of human identity.
And additionally, there is a huge amount of flexibility in the concept beyond anything that is impacted by personal choice, which further illustrates that there isn't really any essentially logical or objective grounds for defining what constitutes a nation and what doesn't - the only criteria is really is whether or not people think of themselves as a nation, and this is again a product both of collective choice and historical development. Take Austria and Switzerland. If someone had asked German-speaking Austrians what their nationality were a hundred years ago, almost everyone would have answered "German". At that point virtually nobody thought of austrian as being a nationality, it was a statehood, and Herr Professor Müller of Vienna thought of himself as German in the same way as his colleagues in Munich as far as that issue was concerned, though he would certainly have regarded himself as Austrian in any issue where political allegiance or statehood was concerned. This is no longer the case. Today, most Austrians regard themselves as belonging to a different nation than the Germans. This is the result of historical experience, above all of the postwar decades when an austrian identity was built around the reconstruction of the country, during which it acquired a number of distinct traits. They could have done that without beginning to think of themselves as Austrians by nationality, but they didn't, so they are.
The Swiss are of course an even clearer example. No objective definition of nationality that includes ethnicity or language could possibly regard Swiss as a nationality, since they are all either German, French or Italian by descent and language (OK, except for the tiny Rhaeto-Romanic inority). Nevertheless, the Swiss do regard themselves as a nation, and so does everyone else.
Finally, just to show how enormously flexible the nationality concept is, there's France. In the whole post-revolutionary era, the French consciously chose to espouse a concept of nationality that rejected ethnicity as a criterion. In principle, "Frenchness" was open to anyone residing in France who accepted the constitution and the principles of the state - in other words, in much the same liberal tradition as America, nationality was essentially turned into a question of adherence to a set of philosophical and political principles, and consciously left "open". This can with some justification be considered a major alternative approach to whole question of nationality. It is often forgotten that it was for many years the dominant one, and that it has more often than not co-existed with the ethnicity-based concept of nationality that we today tend to take for granted, however illogical that seems.
cheers