Well, in short they are of the same genus, but different species. This essentially means that they are closely related, but not too closely, i.e., they have slightly different DNA, morphology (form/structure) and other characteristics.
Ale yeasts are easy. They are simply Saccharomyces cerevisiae.
The taxonomy of lager yeasts seems to be changing over time by scientists. It started out being called Saccharomyces carlsbergensis. Since then lager yeasts have been referred to as Saccharomyces uvarum, Saccharomyces cerevisiae vars uvarum, and Saccharomyces pastorianus.
For simplicity, lager yeasts can be broken down into 2 species: S. uvarum and S. pastorianus. They are both believed to be hybrids:
S. uvarum = S. cerevisiae + S. monacensis
S. pastorianus = S. cerevisiae + S. bayanus
Lager yeasts can metabolize at cooler temperatures than ale yeasts. Correspondingly, they can undergo stress at cooler temperatures than ale yeasts. Lager yeasts also produce different proportions of flavor-active compounds than ale yeasts (sulfur compounds and diacetyl are 2 good examples). Lager yeasts don't bind together as nicely as ale yeast. Therefore, they form smaller colonies and a smaller krausen. The can also ferment a few more sugars than ale yeasts. Ale yeasts cannot ferment melibiose, but lager yeasts can. Ale yeasts can partially ferment raffinose, but lager yeasts can fully ferment raffinose. However, since the quantity of these sugars in wort is so low, it's rarely a noticeable increase in attenuation.