For many centuries, songe used to be the only word to mean "dream" in French. It cames from the Latin somnium which relates to somnus (sommeil, sleep).
Other romance languages have kept somnium as the main word for it (sp:sueño, it:sogno, pt:sonho, cat:somni, ro:somn...).
On the other hand, rêve was created from the verb resver that meant to wander, ramble or prowl. Resver etymology is not firmly established, there are competing theories.
Anyway, rêve had for a long time the negative connotation inherited from resver1 while songe was the neutral and positive word for dream.
Rêve lost its negative side and became more popular than songe in the nineteenth century.

Nowadays, the substantive songe is almost never used in casual French so un rêve and un songe are definitely not interchangeable unless a poetic/literary effect is expected.
The verb songer, while rare, is still used but has shifted its meaning from rêver to penser with a small nuance. Penser means to think (of something) while songer is more like to imagine the eventuality of something, to consider something. Compare:
Je pense me présenter aux élections. : Odds are high it will happen.
Je pense à me présenter aux élections. : I do not forget to do it.
Je songe à me présenter aux élections. : I'm still unsure and likely still weighing up the pros and cons.
We can see that in the songer case, there is still a part of dream in the sense imaginary images or events are showing up in your mind.
Some references:
D’où vient le mot « rêver ? », Marc-Alain Descamps
Rêver
Le mot, la chose, l'histoire, Daniel Fabre
1L’étymologie du mot rêver révèle essentiellement son sens dépréciatif. Rêver, c’est délirer, sortir du sillon. Celui qui rêve, divague et extravague. Le mot rêve semble en effet venir du latin vagus (vagabond, qui erre ça et là, à l’aventure), d’où le verbe esver et resver au XIIIe siècle, « errer, aller ça et là pour son plaisir ». Marc-Alain Descamps