1. Choose an old stamp. I found this one in a Google image search.
Open in Photoshop.

2. We're going to paint out the original image to make a space for a new image.
Select the color of the stamps border by clicking on the eyedropper tool

and then selecting the color you want by clicking a spot in the border area of your stamp with your cursor.

3.Choose a brush size. Mine is a feathered brush of 35 pixels. You can start with a large brush to paint out the middle of the stamp and then switch to smaller brushes for the edge of the image. That's so you don't paint out of the lines. :-)
4. Paint the image out using your mouse. Its tricky at first but after a lot of practice you will begin to get proficient at controlling the mouse.
5. Choose an image for your new stamp. This one is "Bird of Paradise" by a turn of the century illustrator named Warwick Goble. I use old images because they're public domain. Click on the image in the"layers" palette of the new graphic and drag it over the image of the old stamp.
6. This will create two layers on the old stamp. You can close the new image, you won't need it again. Now we need to transform the size of the new image so that it fits with the old stamp just right. Go to "Edit" in your menu bar and scroll down to "Transform" and then over to "Scale".
7.If you need to decrease the new image to fit, choose 90% x 90% in the menu bar and hit "apply". You may need to repeat this step until you get it to the right size. If you need to increase the image, choose 110%x110%.
Photoshop insiders tip: You loose less resolution if you increase or decrease size by 10% at a time.
8. Now we're going to blend in the edge of the new image so that it looks like it belongs there. Be sure you are working on the right layer ( the top layer should be the one that is highlighted in your layers palette).Choose the rectangular marquee in the upper left of the tool bar. Begin in the upper left corner of the new image and gag the marquee down to the bottom right.
9.We'll feather the selection to create a more subtle look. Click on "Select" from the menu bar, scroll down to "feather" and choose 8 pixels. Hit "okay".
10. Now go to "Select" and choose "Inverse". EITHER hit the delete key on your keyboard or go to the menu bar, select "Edit" then "Clear". If you still see some edges use the Eraser tool (in the tool bar) with a feathered brush and clean it up.
11. Add text by selecting the text tool (T in the tool bar), choose a font and size and have fun. I used black text on this sample but the colors can be changed by clicking that color box in the menu. If you want to change color or existing text, highlight the text and change the color in the color box.
note: the menu bar changes depending on which tool you are currently using.
The finished stamp.
Here's another favorite.

And another.
Click here to see a page of finished stamps.