To make it convincing, your going to need photoshop.
But, it's really easy really...
Take a picture of yourself, it's easier if it's against a solid background. I've found a white wall works best for me.
Use the magnet selector tool to select yourself
Copy
Paste yourself in the picture with the celeb. your going to have to do some adjusting to get the proportions right, otherwise someone can end up looking like a giant.
And that's pretty much it. You'll have to do a little tweaking, but it's pretty much that easy.
(Just remember, it's kind of illegal to alter an image that's not your own, or you haven't been given permission to alter)