Tantalums are much more stable than electrolytics, but also more expensive. I would go with the electrolytic caps. These should work fine. Is the psu you are using regulated? If so, you don't need a cap on the input. But if not, or if the psu unit is some distance away, use the cap. It won't hurt anything to use a cap in either instance. If you are using a wall adapter, I would definitely use a cap on the input. Don't forget to put a small value cap in parallel to help filter out the RF (a .1uF mica cap will work fine). Use these where ever you put the electrolytic caps. So, my recommendation would be to go with 47.1uF on input of 5V reg, 10.1uF on output of 5V reg and 10.1uF on output of 3V reg.