**In Photoshop** - `Action` and `Batch`or `Image Processor` is what you need:

http://graphicssoft.about.com/od/digitalphotography/l/blps_batch.htm

So this is how it would basically go:

 1. Make `Action` where you create a new layer at the bottom and fill it with color.
 2. Use `File > Automate > Batch` or ` File > Scripts > Image Processor` to execute that recorded Action to all of the images.


**Edit:**

My bad! 

I got thinking about it and you can also run Actions through ` File > Scripts > Image Processor` as well. But, I'll keep that part about saving image inside Action because that allows you to save it in more formats than `Image Processor`

So instead of `Batch` use `Image Processor`.

____

**Saving image in another format in `Batch`**

Unless cs 5 has way to do this better.. Converting the file format can't be done with batch.

You can however do this:

 - As part of the Action where you create new layer and fill it with color, also save the file with the format you want and to the folder you want,  then
   close the document `ctrl+w` and then go to batch and select destination as `none` and run the Batch.