OK, what you need is a ¨Bump Map¨. A Normal Map is something totally different and very break-trough in the 3D world. Actually, only a few game engines and some very high-end apps can handle Normal Maps.
Back into the BUMP MAP. It is a just a gray scale image. Or any other image with the ¨NO RGB¨ option turned on. Gray areas in the images are left without change. White areas are raised, while black areas are depressed. From the file point of view, it is just a JPG, PNG or TGA file created with any paint program. Anything from Photoshop to MS-Paint cant create such file (of course, your choice will depend on your skills and need paint tools).
What is really important is how the image is mapped into the object. Actually, you shouldn’t start painting your Bump Map untill you know how it is going to be mapped. Search for UV Mapping tutorials, or read the Online Manual for other mapping options.
Once the image is mapped, all that is left to do is loading your paint program and activating the ¨Norm¨ map-to option in the material settings.