When I was explaining what being trans* meant to my step son (eight at the time), I started by asking him "Are you a boy or a girl?" He replied "boy".
I then asked "So did you wake up one day and *decide* to be a boy, or have you always been a boy in your head?" He said that he's always been a boy.
I followed up with "well, people who are transgender have always known that they're whichever gender they are in their head, it's just that they were born into a body whose sex doesn't match what their head is telling them." We then went on to discuss the difference between sex and gender, and how sometimes you need to dress or act a certain way to be comfortable in your skin. (One of his mother's co-workers had begun transitioning shortly before this conversation took place, so we were dealing with the concept of binary trans folk as a starting point.)
He seemed to understand the concept pretty well, though I expect we'll be having more conversations as time goes on. Especially now I'm officially out socially as genderfluid. Step-son is definitely still grappling with the concept that you can't always tell a person's gender just by looking at them.
My three year old currently doesn't know/care about gender roles, but I expect to be having similar conversations as she gets older and realises that most people aren't called "they" and/or most people referred to as "mum" have far more feminine traits than I do.