While I agree with Oliver's judgements, I also think many people are genuinely puzzled about how someone could feel as if they had the wrong sort of body, so let me try to say a few things that might help to clarify it. I should say, however, that I am no expert on these issues, and so I'm sure to get some of the established terminology wrong.
Let's start with a different sort of example. I am of Irish descent. But I do not think of myself as Irish-American. From my point of view, the fact that many of my ancestors lived in Ireland is just that: a fact about my family's past. For other people, however, being of Irish descent is very important to their sense of who they are. They value Irish traditions and customs, participate in Irish celebrations, and so forth. It is, as we say, part of their identity to be Irish-American. And so, if someone tells a rude joke about "the Irish", I wouldn't really take it personally; I'd just dismiss that person as a jerk. Someone who identifies as Irish-American would, on the contrary, rightly feel as if they had been insulted.
Lesson: The "external" facts about one's family are very different from the "internal" facts about one's identity. Ethnicity is not the same as ancestry.
Similar things can be said about gender, though here it gets even more complicated, because there are at least three different things "male" and "female" can mean. First, and most obviously, one might have in mind what we could call "anatomical sex". This is a matter of what sort of external genitalia one has: A penis or a vagina. A closely related but still different notion is what we might call "genetic sex". This is a matter of what kinds of chromosomes one has: XX or XY. But neither the anatomical nor the biological notion is what people have in mind when they speak (in contexts like this one) about gender. That notion of gender is social in character. It has to do not with genetics or anatomy but with social roles and expectations. It is, as people say, socially constructed.
None of these notions is as "clean" as people usually think. It just isn't as simple as XX vs XY; there are intermediate and other states. Anatomically, there are various sorts of hermaphrodites and other combinations, and if we include secondary sex characteristics (breast development, facial hair, etc), things get even more confusing. One should also realize that genetic sex and anatomical sex can come apart, even at birth. Some people who are XY are born anatomically female, due to issues connected to the expression of the so-called SRY protein during fetal development. (This already makes it a very interesting question what it's supposed to mean that marriage must be between "one man and one woman".) As far as social gender is concerned, most people, it is true, strongly identify with the social gender that goes with their anatomy. But some people (the androgynous) don't strongly identify with any gender. (Perhaps you do not, since you say you have "no interest in the notion of 'femininity'".) Other people find themselves identifying with aspects of each gender, either moving between them in different situations (the bi-gendered) or stably experiencing themselves as partly male and partly female (the ambi-gendered).
But what does it mean to "feel female" or "feel male"? Well, the first thing to say is that, when someone who is anatomically female speaks about "feeling male", it is (usually) the social notion that is in play. What they mean is that, as a matter of their own self conception, they identify as male, not as female. OK, so what does that mean? Since the notion of gender in play here is social, we might think, in the first instance, that "feeling male" has something to do with how the person wants to be perceived and treated socially. As we all know, people who "present" socially as male are treated very differently from people who "present" as female. Men and women are expected to like different things, and to do different things, and so forth. So it is easy to understand how someone might feel a kind of "disconnect" between the social role they are assigned, in virtue of presenting as female, and how they feel inside, that is, how they feel they ought to be treated.
Now, the really crucial point is that this can perfectly well be a matter of how one feels, and not just a matter of what one thinks. Although gender is a social notion, it is one that we all internalize through the process of socialization. It isn't at all a matter of what one thinks about gender: whether you think women like hairdos and high heels, to use your example. How we interact with other people is affected simply by our knowing of such stereotypes, even if we reject them, and psychologists and sociologists have gotten very, very good over the last few decades at designing experiments to prove this point.
Here's an example. Suppose you take some kids and ask them to do a moderately difficult math test. Half of them you ask just to put their name at the top; half you ask to put their name and gender. Then the girls in the second group will do worse than the girls in the first group! It doesn't matter if they really think that girls are no good at math. It's enough if they know of the stereotype, and then you remind them that they're girls. What's really amazing is that, if the test is really easy, then the girls in the second group will do better than the girls in the first group. It's as if they're thinking: We'll show them who's bad at math!!
Lesson: Conceptions of masculinity and femininity, and the associated stereotypes, are so deeply ingrained in our brains that, whether we agree with them or not, they shape almost all of our social interactions. (That is not much of a surprise, if you think about it in evolutionary terms.) Now, I'm sure all of us feel, at times, as if society assumes things about us, in virtue of our gender, that don't fit who we are. But can one imagine what it would be like to feel as if society almost always assumed things about us that didn't fit? It would be similar to what would happen if everyone assumed that, since I have red hair and freckles, I must be interested in how the Irish rugby team is doing this year, or that I must love Guinness and soda bread and get real excited about St Patricks Day. (OK, I do love Guinness!) But, of course, compared to how one's gender determines one's life, that would be but a minor annoyance. Surely being treated, as a matter of course, as if you were someone you were not would be very difficult and very painful. (And yes, this does extend to racial stereotyping, too.)
If all of that makes sense, then maybe we can also understand, at least a bit, why someone might want to change their body to conform to the gender with which they identify. It isn't, in the first instance, as if they feel they have the wrong body. In the first instance, it's a matter of their self-identity: who they feel they are and how they relate to others socially. But, although anatomical sex and gender are two different things, matters concerned with the body are about as central to how our society understands gender as anything could be. So, as part of feeling as if one is really male, not female, one might well also feel as if one had the wrong kind of body. In fact, not all trans-gendered people do feel that way, though many do.
So, well, I hope that helps.