Tezuka's 1949 manga, Metropolis, features Michi, a synthesised human with a gender switch which can turn it from a boy into a girl and vice versa which is used as a plot device.
Tezuka's 1953 manga, Ribbon no Kishi (Princess Knight) features a reverse trap with a girl pretending to be a guy:
Taking place in a medieval European-like fairy-tale setting, Princess Knight is the story of young Princess Sapphire who must pretend to be a male prince so she can inherit the throne (as women are not eligible to do so). This deception begins as soon as she is born, as her father the King announces his baby is a boy instead of a girl. The reason for this is that the next-in-line to the throne, Duke Duralumon, is an evil man who would repress the people if he were to become king, and because of this the King will go to any length to prevent him from taking over.
Similarly, The Rose of Versailles (1972) is another that has a girl, pretending to be a guy, Oscar François de Jarjayes.
For a "straight" trap, 1973's Ara Waga Tono! appears to be the first to fit the bill.
This is a slapstick romance, where girls and boys clash in a ‘modern’ co-ed high school. There is a lot of romantic intrigue, quite a bit of gender-bending and some teenage angst when adults Just Don’t Understand. (source: goldbird)
Then there's 1974's Oira Sukeban:
Oira Sukeban (おいら女蛮?), sometimes called Sukeban Boy, is a Japanese manga created by Go Nagai in 1974. It is a comedy with several erotic touches, where the protagonist Banji Suke (or Sukeban) has to disguise himself as a girl in order to be able to attend an all-female school. As Suke Ban is a rebellious boy, this situation creates several comedic troubles.
The manga was adapted to an OVA in 1992 and was released by ADV Films in the US under the name Delinquent in Drag.
But my guess is that the trope really took off only after the publication and airing of Ranma ½ in the late 80s.
The story revolves around a 16-year old boy named Ranma Saotome who was trained from early childhood in martial arts. As a result of an accident during a training journey, he is cursed to become a girl when splashed with cold water, while hot water changes him back into a boy.
Ranma ½ had a comedic formula and a sex changing main character, who often willfully changes into a girl to advance his goals. The series also contains many other characters, whose intricate relationships with each other, unusual characteristics and eccentric personalities drive most of the stories. Although the characters and their relationships are complicated, they rarely change once the characters are firmly introduced and settled into the series.