Pretty much you should be able to insert your favourite OS DVD or CD into the drive and you should be able to either change the boot order in the BIOS to make the machine boot from CD or you may have a "boot manager" option on your BIOS startup screen.
Almost every machine I've seen these days has a boot manager.
After that you should simply be able to follow the normal method to install your OS over the DOS install.
-=EDIT=-
To answer your edit, for Windows Vista and Windows 7 you will not likely get a choice about drive format, they will use NTFS by default, and for Windows XP NTFS would be best as it will support the security controls the OS works with.
On Linux the choice is somewhat arbitrary as there are a whole selection of filesystems to use, the standard is ext4 these days and should be considered good and stable, but there are lots of slightly different systems which have subtle performance differences (I believe ReiserFS works better with many small files). Generally whatever OS you install will have a pretty reasonable default choice that you might as well stick with.