You can use any graphics file format as long as it is supported by the Python Image Library and as long the graphics file has one of the TTD palettes applied.
What image files should I use?
If you are unsure about what file format to use, take PNG as a safe bet. It can work with palettes and has the added advantage that it can be viewed by browsers and as such, you can just upload your sprite files to the forums if you want to show them. PNG files are also widely supported by graphics editors.
What is this palette business?
Graphics for TTD can only use a limited set of colours (OpenTTD 32bpp graphics are an exception to this; while NML can handle these for you, it is not covered in this tutorial). Check the NewGRF Specs for what these palettes are and which colours are available to use. The DOS palette has a few more colours, so if you are still in the position to choose, go for that.
In theory, you can draw in true colour (24 or 32 bpp) and then convert your result to the TTD palette, but that usually does not work out too well. It is best to only use the colours from the palette in the first place. Each sprite should get a blue background, for which you use the blue from index 0 (indicated as "Transparent" on the page of the link above, or hex colour #0000FF).
Make sure to actually save the graphics files with a palette applied, or NML will complain that you do not have one. If you do not have this palette, you can extract it from any decoded GRF file or download a premade palette file.
See Save paletted image files for how to create image files with the correct pallete applied.
How do I draw sprites?
This tutorial is not about drawing, but about coding once you have drawn. If you want to learn how to draw sprites, check the GraphicsTutorial.