X-Men Origins: Wolverine is actually not part of the MCU. It’s part of the X-Men film series, produced by 20th Century Fox.
Prior to Deadpool (2016), that was Wade Wilson/Deadpool’s only appearance on the silver screen, so no, we haven’t seen that character in the MCU. (In short, 20th Century Fox owns the movie rights to “mutants” from Marvel Comics, which includes Deadpool.)
In Origins, Wade Wilson is part of the mutant mercenary group including Wolverine, Sabretooth, and Will.i.am from the Black-Eyed Peas. Later in the movie, he is both imbued with the powers of several deal mutants by Major Stryker (making him “the dead pool”), and (as the Deadpool teaser trailer noted) inexplicably has his f—ing mouth sewed shut. He fights Wolverine on top of a cooling tower and gets his head chopped off, although because he has a healing power like Wolverine’s, this may not have mattered very much.
The upcoming Deadpool movie is also part of the X-Men film series (it has Colossus in it!), and so theoretically shares continuity with Origins, but it will essentially ignore that film entirely in relation to Wade Wilson/Deadpool’s character history.