Faits: A. E._ et F._ ont été propriétaires en hoirie, jusqu'au mois de septembre 2011, de la parcelle 6540 du registre foncier de Lausanne, sise à l'avenue Charles-Secrétan 32. Ce bien-fonds, d'une surface de 1'677 m2, supporte un bâtiment d'habitation de quatre appartements, construit au début du XXème siècle. Ces appartements (au total : 1'086 m2 de plancher habitable) sont occupés par les locataires, notamment, au 3ème étage, par A._ et B._. La maison est entourée d'un jardin, sur deux niveaux: la partie supérieure entoure le bâtiment et la partie inférieure, en contrebas, en est séparée par un mur de soutènement. Il n'existe pas de places de stationnement pour automobiles sur la parcelle. Dans le quartier desservi par l'avenue Charles-Secrétan et l'avenue Auguste-Verdeil, la parcelle 6540 et toutes les parcelles voisines figurent sur le plan "Recensements architectural, des jardins d'intérêt historique, des ensembles bâtis" comme des jardins d'intérêt historique, note 3. Cette note signifie que l'objet est d'importance locale (note 1: importance nationale; note 2: importance régionale; note 3: importance locale; note 4: qualité d'intégration). E._ et F._ ont décidé de mettre leur immeuble en vente. Le 16 juin 2011, elles ont conclu avec C._ et D._ un contrat de vente à terme conditionnelle. Puis, par acte authentique du 31 août 2011, les parties au contrat de vente ont requis du registre foncier l'inscription du transfert de la propriété de l'immeuble. B. Avant la vente de l'immeuble, E._ et F._ ont soumis à l'administration communale, le 20 janvier 2010, une demande de permis de construire en vue de la création de huit places de parc extérieures, dans la partie sud du jardin de leur immeuble (partie inférieure), le long de la limite de la parcelle, avec un accès au domaine public, d'une largeur d'environ 4 m. La réalisation de l'accès implique la suppression d'un arbre existant, un hêtre dont le tronc a un diamètre de 85 cm. A cet endroit, à l'entrée du jardin inférieur, il se trouve un espace de 6 m environ entre la limite de la parcelle voisine et le mur de soutènement de la partie supérieure du jardin. Le hêtre est planté sur cette bande de terrain, à 3 m environ de la limite de propriété. Le projet a été mis à l'enquête publique du 19 février au 22 mars 2010. Le 22 mars 2010, les huit locataires de l'immeuble, notamment les époux A._ et B._, ont formé opposition, en invoquant en substance l'intérêt à la protection du patrimoine et en faisant valoir que l'intérêt financier ou de convenance personnelle des propriétaires ne pouvait pas l'emporter. Ils exposaient également qu'il n'y avait pas d'obligation, dans le règlement communal, de créer des places de stationnement pour résidents en l'absence d'un projet de nouvelle construction ou de transformation de leur bâtiment; eux-mêmes se déclaraient satisfaits de l'organisation communale du stationnement sur le domaine public. Par une lettre du 3 juin 2010, le chef d'unité administrative de l'office de la police des constructions de la ville a informé l'architecte de E._ et F._ des résultats de l'enquête publique; en particulier, il a résumé l'opposition précitée. Puis il a rappelé que, dans un premier temps, une entrée en matière favorable pouvait être envisagée, mais comme à l'issue de l'enquête publique, tous les résidents du bâtiment s'opposaient au projet, cela signifiait que le besoin en places de stationnement n'était pas avéré. L'office de la police des constructions s'est ainsi déclaré "pas en mesure de poursuivre un préavis favorable à la municipalité". L'avocat des deux propriétaires a répondu à l'office de la police des constructions par courrier du 23 juin 2010. Il a notamment indiqué que les acquéreurs potentiels de l'immeuble, entendant constituer une PPE et affecter les appartements à leur propre usage ainsi qu'à celui des membres de leur famille, insistaient pour qu'un nombre de places de parc suffisant soit aménagé sur la parcelle 6540. Il a par ailleurs produit la copie d'une lettre envoyée le 3 octobre 2009 par A._ à E._, faisant une offre pour l'achat de l'immeuble avec la "condition impérative", pour la validité de l'offre, de l'obtention du permis de construire les places de parc. Le chef de l'office de la police des constructions a écrit le 1er décembre 2010 à l'avocat de E._ et F._ que le service de l'urbanisme avait revu sa position initiale négative; un préavis positif allait donc être soumis à la municipalité de Lausanne. C. Au cours de sa séance du 8 décembre 2010, communiquée aux opposants le 23 décembre 2010, la municipalité a accordé à E._ et F._ le permis de construire requis. Elle a ainsi autorisé la création de huit places de parc extérieures, avec des aménagements extérieurs, liées au besoin du bâtiment principal, ainsi que l'abattage d'un hêtre. Les époux A._ et B._ ont porté leur cause devant la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud (ci-après: le Tribunal cantonal). Après avoir procédé à une inspection locale, le Tribunal cantonal a rejeté leur recours, dans la mesure où il était recevable, et confirmé la décision de la municipalité du 23 décembre 2010. Dans leur arrêt du 21 novembre 2011, les juges cantonaux ont considéré en substance que l'aire de stationnement ne pouvait être qualifiée de démesurée et que, d'un point de vue objectif, le besoin de places de parc était établi. Par ailleurs, l'abattage du hêtre ne modifiera pas sensiblement l'aspect du quartier et les intérêts des constructeurs étaient de toute façon prépondérants. D. Agissant par la voie du recours en matière de droit public, les époux A._ et B._ demandent au Tribunal fédéral d'annuler l'arrêt du Tribunal cantonal du 21 novembre 2011 et de renvoyer la cause à la cour cantonale pour nouvelle décision dans le sens des considérants. Les recourants se plaignent pour l'essentiel d'une constatation arbitraire des faits, d'une violation de leur droit d'être entendus ainsi que d'une application arbitraire du droit cantonal. Le Tribunal cantonal a renoncé à déposer des observations. La municipalité de Lausanne conclut au rejet du recours. Les intimés concluent également au rejet du recours, dans la mesure où il est recevable. Les recourants ont répliqué le 20 février 2012; ils maintiennent leurs conclusions. Par ordonnance du 23 janvier 2012, le Juge présidant de la Ire Cour de droit public a admis l'effet suspensif des recourants.