Being trans is almost an ineffable experience. Like Jennifer said, we can't really say what it feels like, per se, just that something is terribly wrong (gender dysphoria), like someone said previously, we have a software/hardware mismatch. Things may feel better for us if we do certain things to alleviate the dysphoria like dressing how we want instead of how society expects us to dress, engaging in certain activities that we think are typically cross-gender, changing how we look physically, augmenting our voices in one direction or another, or eventually seeking medical intervention.
I will throw in a caveat about "cross-gender activities," though: I don't think an activity is inherently masculine or feminine, but sometimes we perceive them to be due to cultural conditioning. For instance, if this were the fifties, women stayed home and did the cooking, cleaning, child rearing, et cetera, whilst men went out and worked bringing home the money at jobs that included tough manual labor or, for some, things of a more white-collared nature. I like doing almost all of the typically feminine things like cooking, cleaning, sewing, and what have you from a very young age to the extent that I still think I'd make a really good housewife, but I'm also an engineer and I love to take things apart and put them back together whilst devising even better or entirely new designs along with building systems and solving problems. Nowadays, women can pretty much do what they want in any fashion activity wise, but men are unfortunately still looked down upon for engaging in what is thought of as traditional feminine activities. I remember when I was a child that I really wanted a Barbie but when I asked my mother, I was reamed out about how boys don't pay with Barbies and to never mention anything of the sort to my father. I was lucky enough to have a many female childhood friends who let me play with theirs. Instead of Barbies and dolls, I got Batman and cars, but I did manage to get lots of stuffed animals, which, to this day, I still collect.
It's kind of like trying to run out of date firmware or drivers and the system keeps crashing. At some point, it is nearly impossible to cope and the system shuts down resulting in depression, anxiety, phobias, other mental health issues, suicidal ideation, attempts, or complete follow-through. If I remember my statistics correctly, nearly one in two (somewhere around forty-four percent) transgender people attempt suicide in their lifetime with a remarkably high recurrence rate. On occasion, some people, myself included, will jump into a really gendered activity like bulking up at the gym or in the case of Bruce Jenner (I saw the interview, but I have yet to read the thread in its entirety) did and became an athletic powerhouse, all in the name of or subconscious effort to run from our problems. It gives us something to focus instead of the feelings of incongruency. This usually ends up backfiring from what I've heard and I consider my attempts at escape to be something that hurt me somewhat in the long run.
The general theory is that transgenderism is partially caused by both genetics and prenatal hormone levels. It also has links to other mental health issues (and I hate how being trans is classified as a mental health issue), which I have a few of my own theories on. In utero, cis people have all of their genetics and hormones matching up at the right time in the right quantities. With trans people and, if I recall based on the last research papers I read, homosexuals don't have everything matching up at the right time in the right quantities to make us cisgendered and straight. The general amounts of testosterone and estrogen to which one was subjected to in the womb can be roughly determined by the index and ring finger digit ratios. Mine, being on the female range as well as many gay men also fitting into that range. The reverse is true of female to male trans people as well as many lesbians. Androgynes aren't really represented in any of the research that I've been able to scrounge up, unfortunately. That being said, our brains aren't cisgendered brains. My brain resembles a female brain in many ways, but not all. Hormone therapy also influences gendered brain differences. For example, estrogen will affect a male brain making it more female over time. I was lucky enough to have a brain scan before I started HRT for other reasons unrelated to being trans and parts of it were definitely in the female range. So, we end up being subject to bodies and hormones (during puberty) that are unlike those we were exposed to at certain times in utero that, essentially, start to make us crash resulting is thoughts and behavior unbecoming to how we feel we should actually be because the preloaded software is barely compatible with the hardware. It runs, but it runs poorly. In many if not most cases, cross-gender hormones alleviate gender dysphoria.
The Computer Analogy:
Nota bene: Know that this is an imperfect analogy, but I'm trying to make it easily understood even though I know it could be better and I'm trying to keep it as simple as possible. If you know about overclocking and whatnot, please just bare with me because I know it's more complicated that I've set it out to be with timings and other things. I'm going for ease of use, not specific technicalities.
The brain is the processor (CPU).
The way the person feels is the RAM.
The motherboard is the primary body as in the skeleton and all essential organs such as the heart, lungs, liver, et cetera.
The sex hormones are the power supply (PSU).
The secondary sex characteristics and reproductive organs are the video cards.
In utero, that is in the factory where the computer is made, the computer is assembled using the parts above except for the video cards. The fetus only has on-board graphics at the moment, meaning it's prepubescent. The assembly drawing with the parts list is incorrect and the wrong processor (the brain is affected by prenatal hormone levels) is inserted to the motherboard. It still works, but it's like getting an i3 instead of the i7 that you wanted. You also get some really crappy RAM sticks that have just enough memory to function. The power supply is inserted but set at the wrong voltage resulting in some early childhood issues of not feeling all that right in regards your body versus your gender, but you don't need all that much wattage, so it's tolerable and it's hard to explain to people.
When you hit puberty, it's as if the manufacturer sends you a package of self-installing Radeon graphics cards. The fact is, you really wanted nVidia cards instead. The problem now is that you require more voltage and wattage to run all these components, so the power supply ramps up (increase in sex hormones opposite from the ones you want) both of them but your voltages are higher than they should be affecting how the RAM and CPU work leading to system crashes (gender dysphoria). In order to deal with all of these issues, you decide to overclock the ram and the processor because you can't actually change the voltage yourself. This would be akin to trying to run from the dysphoria. If nothing is done about these issues, it results in the computer burning out and depression sets in or suicide is committed.
In order to combat these, cross sex hormones are used. You get a new fancy power supply set at the correct voltage. This reduces the stress on CPU and the RAM, but you're still stuck with some Radeon cards, but you feel better compared to before. Now that one of the issues has been solved as best it can, you can upgrade to a new processor, maybe an i5 or i7 depending on how the new hormones affect you. It also allows you to get some new RAM so you can deal with life again without as many system crashes. Now, let's say you're running Crossfire with your Radeon cards and want to swap them out for nVidia because you think you'll feel better with them instead (sex change or SRS). So, if you're FtM, you'll get a mastectomy and a phalloplasty and be pretty good to go with some GTX 860s, but it's not like you're getting water-cooled Titan Xs (akin to being born the sex you wanted instead). If you're MtF, you end up growing in a nice pretty pair GTX 860s, or if you have large breasted women in your family, GTX 970s and getting vaginoplasty. It's not as good at the water-cooled GTX Titan Xs, but it does the job and you're happy with it. This "upgrade" is called "transitioning." Bye, bye gender dysphoria.
Mind you, this doesn't really take into account the social aspects of transitioning or being trans like losing your job, having regrets, being disowned, et cetera. I hope it suffices for the time being, though.