The first step is, of course, to choose what you want to have as a seal. You can use kanji, a mix of kanji, western words, emblems. Whatever. Just understand that whatever you do, the seal can be positive or negative (in the picture above, for example, there are two positive and two negative images - positives have the ideogram lines in red, while the negatives have white lines and red background).
Assuming you went for something written in Kanji, you may obviously use one of the numerous online dictionaries to get the correct kanji symbols.
My choice was one of the "four words idioms": Fu-Gen-Ji-Kou that is "Actions speak louder than words" (不言実行).
If you opt for Tensho - that is the thin, stylized style used mostly for seals (in it lines are more or less the same width, because while the other styles use a brush, Tensho was mostly used for engraving) you may find some problems translating your Japanese in a "Tensho font".
So far the only one I found is the one kindly provided by Hiroyuki Nagashima.
From that, (just write the kanji in the small text field in the blue area) I get back:
I want a square seal, so I rearrange the 4 ideograms:
and add a border around.
Now, this is more or less ok, but the real seals have usually imperfections having been engraved in wood or stone or whatever the material is.
I am not very good with graphics, and I don't own any kind of advanced graphic package, so I called my friend Barbara for help, and asked her to have a look at an article on how to make "electronic seals"
Basically it explains how to apply distortion effects so that the lines are not too "perfect" (the article goes in more detail in case you want to have the result as an image to sign your digital pics or documents with, and includes advice on how to get the "ink" part look more natural, but if you want a real stamp, you can be content with the distortion part).
Here is the result after Barbara's help:
She actually was so nice as to provide the results both in jpeg and Adobe Illustrator format. The latter is advisable if you have a small seal with lots of intricate details. You better discuss this with the company that will create the actual stamp.
In my case, I had great results with "Mondotimbri". They are located in Italy so depending where you live you may want to check someone closer, but for me they provided excellent service.
This one is their largest self-inking model (43 millimeters on the side), because I wanted a large seal for large scale works, along with a scan of the actual result when used on paper: