You can use them interchangeably in many situations. If I had to make a difference, I would say "Zug" more explicitly refers to the physical train (locomotive + a couple of cars attached), while "Bahn" (or "Eisenbahn" if you're talking about a railroad rather than say a subway train) is used to talk about the railway system. There's a lot of leeway here though. I'd probably use "Bahn" also to refer to trams (or trolley cars if you're in the US), and I wouldn't call them "Zug".
Interestingly, the German Wikipedia page for Eisenbahn has links to sister pages in 70 other languages - but not English! Usually this happens because the concept doesn't exactly translate 1:1. The closest meaning I can find is "railway system" as 'kpas' said, including the infrastructure (tracks, stations) as well as the trains and carriages.
If you want to test your German, have a go at reading the article, especially the paragraph on Etymologie which discusses the different naming convention vs. other languages! It also mentions that "Bahn" is a common abbreviation for "Eisenbahn" - but the German Wikipedia page for Bahn includes Eisenbahn as a subcategory, separate to S-Bahn and U-Bahn systems. So perhaps "heavy rail system" is the best technical translation for Eisenbahn, but Bahn includes the latter types too..
So are you a native German speaker, @kpas? Can you, or any other native speaker, confirm that Bahn is used in Germany and/or Austria to mean "train" rather than "railway system"? Apart from, that is, in DB (Deutsches Bundesbahn) advertising. They seem to use Bahn in a fairly broad way, but even they seem to use Zug when talking about a train.
I second the voices stating that 'Bahn' means a pathway in a more broad sense. Interestingly, the word 'trajectory' is 'Flugbahn' in German - the path something flies through the air? (And I find this entertaining because in Hungarian we use mirror translations of this concept. :3 Language learning is fun!)
'A new railway' is accepted as a correct answer. I think it is less confusing to use Bahn for 'railway' and Zug for 'train'. You do need to keep in mind that the word 'Bahn' can refer to railways ('Eisenbahn') but also to subways (which are called 'U-Bahn', short for 'Untergrundbahn') and to trams ('Straßenbahn', in some areas 'Trambahn'). An additional complication is that the German railway operator DB ('Deutsche Bahn') quite regularly refers to itself as 'Die Bahn'; in fact, their German website is www.bahn.de (and their website in English is www.bahn.com).
Sure, I hear it all the time. No idea about relative prevalence. It's possibly more informal. I also feel like it refers more to 'the scheduled service' rather than 'the vehicle itself', in the sense that you could say unsere Bahn hat Verspätung but not alle Bahnen von DB sind rot und weiß.
Adjectives that come before the noun must have their endings changed to match the noun according to some rules. This is called "adjective declension": http://yourdailygerman.com/2012/10/08/adjective-declension-german/
Although die Bahn is most frequently used to refer to a train line or railway line even loosely as a train (der Zug), don't forget that it also has other meanings, eg tram, street car, (building) station, a lane, a race track or course, a strip of paper or cloth, even a flight path... See Hueber Worterbuch Deutsch als Fremdsprache. Happy reading! I entered my answer as "a new station" and was marked wrong. Solche ist das Leben!