According to Chapman & Kipfer, Dictionary of American Slang, Third Edition (1995), the interjection "my bad" arose in the 1990s and its source is "teenagers":
my bad interj 1990s teenagers: My bad: My fault or my mistake. A term of apology. —Daily Record
I first heard "my bad" used (in the San Francisco Bay Area of California) around 1994 from a college-age person in the context of a turnover—an errant pass, I believe—committed during a pickup game of basketball.
Inspired by tchrist's excellent addition to his answer, I checked the Elephind newspaper database to discover its earliest instance of "my bad." The earliest appears to be from the "Unclassifieds" section of the [Washington, D.C.] American [University] Eagle (February 8, 1988):
And "Dove Bars At Night Horowitz": Are you related to.... No? Oh, well, my bad. What do you mean, "on my own?!" That's not nice. As my mother always said, "Remember what Thumper's mother said?" My mother wasn't very original. She wasn't as bad as my dad though, he quotes Bill Cosby. -Jesus
This instance corroborates tchrist's citations indicating that "my bad" was in use in parts of the United States in the 1980s. It also provides explicit evidence that the expression had entered college slang (at one Washington, D.C. university, anyway) by early 1988.
In addition, it may be the first identified instance of "my bad" that has no connection to sports. The second and third instances cited by tchrist (from 1986 and 1987) are clearly sports related, and the first instance (from 1985) probably is: Although the wording ("Oops, my bad, I forgot for a moment what the Commodore did to Georgia. Silly me.") is rather opaque, I'm pretty sure that it refers to college football, given (1) the time of year (November 14), and (2) the fact that Gainesville is the home of the University of Florida, which (3) is a traditional rival of the University of Georgia, both of which (4) play in the NCAA's Southeast Conference, as does Vanderbilt University, whose team is called the Commodores, and which (5) pulled off a shocking 13–13 tie against the heavily favored University of Georgia team on October 19, 1985. Perhaps the Florida writer alluded to that earlier game in response to gloating from one or more Georgia fans, because on November 9, Georgia had defeated Florida (which had been ranked number one in the nation prior to the game), 24–3.