What is the difference between DynamicMapServiceLayers and TiledMapServiceLayers?
A dynamic layer generates an image each time the map view changes - panning and zooming, turning sublayers on/off, etc. This image is then served in your map viewer.
A tiled layer is pre-cached on the server, as a series of small images optimised for each zoom level - as you change the zoom level, a different set of image tiles displays. This allows the server to display the information very quickly (as with the background tiles on Google Maps).
Do separate services need to be published to use each type for a single map?
Typically a dataset would be more suited for one format over another (eg a geology layer is probably quite complex and doesn't change very often, therefore it would be suitable for caching) but there's no reason why you couldn't also serve this as a dynamic layer.
You should create a separate non-cached service in this case.
Are both valid types one can use in Esri's FLEX API?
Yep, you can use either type. Note that there is also the option to stream vectors directly to the client as feature layers.