Sachverhalt:
A. A._, seine Lebenspartnerin B._ sowie ihre gemeinsamen minderjährigen Kinder C._, D._ und E._ sind mazedonische Staatsangehörige. Sie lebten in X._ und gehören der Volksgruppe der Roma an. Nach ihren Angaben verliessen sie am 22. März 2010 ihren Heimatstaat und gelangten am 24. März 2010 in die Schweiz, wo sie gleichentags um Asyl ersuchten.
B. Mit Verfügung vom 19. Mai 2010 stellte das Bundesamt für Migration (BFM) fest, die Gesuchsteller erfüllten die Flüchtlingseigenschaft nicht. Es lehnte die Asylgesuche ab und ordnete die Wegweisung aus der Schweiz sowie deren Vollzug an.
C. Die von den Gesuchstellern dagegen erhobene Beschwerde wies das Bundesverwaltungsgericht (Abteilung V) am 19. März 2012 ab.
D. A._, B._ sowie C._, D._ und E._ führen Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Hauptantrag, das Urteil des Bundesverwaltungsgerichts sei aufzuheben; es sei bezüglich aller Beschwerdeführer die Flüchtlingseigenschaft festzustellen und ihnen Asyl zu gewähren; eventualiter seien sie zufolge Unzulässigkeit, Unzumutbarkeit und Unmöglichkeit des Wegweisungsvollzugs in der Schweiz vorläufig aufzunehmen. Zudem stellen sie den Eventualantrag, die Angelegenheit sei zur Ergänzung der Untersuchung und neuen Entscheidung an die Vorinstanzen zurückzuweisen.
E. Das Bundesverwaltungsgericht hat sich vernehmen lassen mit dem Antrag, die Beschwerde abzuweisen.
Das BFM beantragt unter Hinweis auf seine Verfügung ebenfalls die Abweisung der Beschwerde.
Die Beschwerdeführer haben eine Replik eingereicht.
F. Mit Verfügung vom 10. Mai 2012 hat der bundesgerichtliche Instruktionsrichter der Beschwerde aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 Gegen den angefochtenen Entscheid ist gemäss <ref-law> die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegeben.
1. 1.1 Gegen den angefochtenen Entscheid ist gemäss <ref-law> die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegeben.
1.2 1.2.1 Nach Art. 83 Bst. d Ziff. 1 BGG ist die Beschwerde unzulässig gegen Entscheide auf dem Gebiet des Asyls, die vom Bundesverwaltungsgericht getroffen worden sind, ausser sie betreffen Personen, gegen die ein Auslieferungsersuchen des Staates vorliegt, vor welchem sie Schutz suchen.
Diese Gegenausnahme wurde mit Bundesgesetz vom 1. Oktober 2010 über die Koordination des Asyl- und des Auslieferungsverfahrens, in Kraft seit 1. April 2011 (Koordinationsgesetz; AS 2011 925 ff.), neu in das Bundesgerichtsgesetz eingefügt. Das Koordinationsgesetz stellt einen Mantelerlass dar. Damit wurden ausschliesslich das Bundesgerichtsgesetz, das Asylgesetz (AsylG; SR 142.31) und das Rechtshilfegesetz (IRSG; SR 351.1) geändert.
Auslöser der Revision waren Probleme, die bei parallelen Asyl- und Auslieferungsverfahren auftraten. Diese Verfahren fallen in die Zuständigkeit zweier verschiedener Bundesämter. Das BFM entscheidet über Asylanträge, das Bundesamt für Justiz (BJ) über Fahndungs- und Auslieferungsersuchen. Der Asylentscheid kann an das Bundesverwaltungsgericht weitergezogen werden, der Auslieferungsentscheid an das Bundesstrafgericht. Gegen den Entscheid des Letzteren ist in besonders bedeutenden Fällen die Beschwerde an das Bundesgericht gegeben (<ref-law>). Sowohl im Asyl- als auch im Auslieferungsverfahren gilt der Grundsatz des Non-Refoulement. Danach darf niemand in einen Staat ausgeschafft werden, in dem ihm Folter oder eine andere Art grausamer und unmenschlicher Behandlung oder Bestrafung droht. In beiden Verfahren muss somit die konkrete Gefährdung der betroffenen Person im Verfolgerstaat abgeklärt werden. Da unterschiedliche Behörden zum Entscheid zuständig sind und ein abweichender Rechtsmittelweg besteht, waren widersprüchliche Asyl- und Auslieferungsentscheide möglich.
Mit der Revision wurden folgende Massnahmen zur Behebung der Koordinationsprobleme umgesetzt: Das Bundesgericht ist neu in parallelen Asyl- und Auslieferungsverfahren letzte Beschwerdeinstanz. Für die Asylverfahren wird zudem das Beschleunigungsgebot verankert. In beiden Verfahren besteht ferner neu die Pflicht der Behörden zum gegenseitigen Aktenbeizug.
Die Zusammenführung des Asyl- und des Auslieferungsverfahrens auf der Stufe des Bundesgerichts erlaubt eine widerspruchsfreie Rechtsprechung unter Beachtung des Gebots des Non-Refoulement. Eine begrenzte Zahl von Asylsuchenden kann somit den Entscheid des Bundesverwaltungsgerichts vom Bundesgericht überprüfen lassen. Der Zugang zum Bundesgericht ist dabei im Unterschied zum Auslieferungsverfahren nicht auf besonders bedeutende Fälle beschränkt.
Wie die Beschwerde an das Bundesgericht bezwecken auch die weiteren Massnahmen eine bessere zeitliche und inhaltliche Koordination der Asyl- und der Auslieferungsverfahren. Mit dem Beschleunigungsgebot soll sichergestellt werden, dass die Asylbehörden dem Asylgesuch hohe Priorität einräumen, wenn die betroffene Person gleichzeitig Gegenstand eines Auslieferungsverfahrens ist. Mit der Pflicht der Behörden zum gegenseitigen Aktenbeizug soll sichergestellt werden, dass sich sowohl der Asyl- als auch der Auslieferungsentscheid bei der Frage der politischen Verfolgung auf die gleichen Informationen stützt (Botschaft vom 24. Februar 2010 zum Bundesgesetz über die Koordination des Asyl- und des Auslieferungsverfahrens, BBl 2010 1469 ff.; THOMAS HÄBERLI, in: Bundesgerichtsgesetz, Basler Kommentar, 2. Aufl. 2011, N. 132a ff. zu <ref-law>).
1.2.2 (Ersuchen des Justizministeriums der Republik Mazedonien um Auslieferung der Beschwerdeführerin 2 zur Vollstreckung einer Freiheitsstrafe. Keine Versetzung der Beschwerdeführerin 2 in Auslieferungshaft.)
1.2.3 Gegen die Beschwerdeführerin 2 liegt demnach ein Auslieferungsersuchen des Staates vor, vor welchem sie Schutz sucht. Sie kann deshalb gemäss Art. 83 Bst. d Ziff. 1 BGG den vorinstanzlichen Entscheid anfechten.
Anders verhält es sich in Bezug auf die Beschwerdeführer 1 und 3-5. Soweit sich die Vorinstanz mit diesen befasst hat, betrifft ihr Entscheid keine Person, gegen die ein Auslieferungsersuchen vorliegt. Die Beschwerde ist daher gemäss Art. 83 Bst. d Ziff. 1 BGG unzulässig.
Dies bestätigt Folgendes: Die Eltern des Beschwerdeführers 1 reisten zusammen mit den Beschwerdeführern in die Schweiz ein und ersuchten ebenfalls um Asyl. Das BFM lehnte das Gesuch der Eltern ab. Die von diesen dagegen erhobene Beschwerde wies das Bundesverwaltungsgericht ab. Diesen Entscheid konnten die Eltern unstreitig nicht beim Bundesgericht anfechten, da kein Auslieferungsersuchen gegen sie vorliegt. Für die Beschwerdeführer 1 und 3-5 kann nichts anderes gelten. Diesen kann die Beschwerde an das Bundesgericht nicht einzig deshalb offenstehen, weil die Vorinstanz insoweit keinen separaten Entscheid gefällt hat.
Auf die Beschwerde der Beschwerdeführer 1 und 3-5 wird demnach nicht eingetreten.
1.2.4 Der bundesgerichtliche Entscheid kann sich in einem Fall wie hier bei Bejahung der Flüchtlingseigenschaft auf die Angehörigen allerdings auswirken. Diese können gegebenenfalls gemäss <ref-law> Familienasyl erhalten.
1.3 Die Beschwerdeführerin 2 hat am Verfahren vor der Vorinstanz teilgenommen. Sie ist durch den angefochtenen Entscheid besonders berührt und hat ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung. Sie ist deshalb gemäss <ref-law> zur Beschwerde befugt (vgl. ebenso Botschaft zum Koordinationsgesetz, BBl 2010 1483).
1.4 Der vorinstanzliche Entscheid stellt einen nach <ref-law> anfechtbaren Endentscheid dar.
1.5 Die weiteren Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Auf die Beschwerde der Beschwerdeführerin 2 ist - unter Vorbehalt der folgenden Erwägungen - einzutreten.
2. Liegt gegen die asylsuchende Person ein Auslieferungsersuchen im Sinne des Rechtshilfegesetzes vor, so ziehen gemäss <ref-law> in der Fassung gemäss Koordinationsgesetz die Rechtsmittelinstanzen für den Beschwerdeentscheid im Asylbereich die Akten aus dem Auslieferungsverfahren bei.
Unter Hinweis auf diese Bestimmung hat das Bundesgericht das BJ eingeladen, ihm die Akten aus dem Auslieferungsverfahren zukommen zu lassen. Dies hat das BJ getan. Gleichzeitig hat es dem Bundesgericht mitgeteilt, betreffend das Auslieferungsersuchen beabsichtige es, bis zum Entscheid des Bundesgerichts in der vorliegenden Sache keine weiteren Schritte zu unternehmen.
Das Bundesgericht hat ebenso die Akten des BFM und der Vorinstanz beigezogen.
Dem Antrag der Beschwerdeführerin auf Beizug sämtlicher Akten ist damit Genüge getan.
3. Die Beschwerdeführerin erachtet ihre ergänzende Befragung als notwendig.
Die Vorinstanz kommt zum Schluss, es sei nicht einsehbar, inwiefern das BFM das rechtliche Gehör der Beschwerdeführerin verletzt und den Sachverhalt unvollständig festgestellt haben sollte (angefochtener Entscheid S. 8 f. E. 4.3). Dem ist zuzustimmen. Das BFM hat die Beschwerdeführerin zweimal einlässlich befragt. Es ist nicht erkennbar, welche zusätzlichen Erkenntnisse ihre nochmalige Befragung bringen könnte.
Die Beschwerde ist im vorliegenden Punkt offensichtlich unbehelflich.
4. Das Gleiche gilt, soweit die Beschwerdeführerin eine Verletzung der Begründungspflicht durch die Vorinstanz rügt. Die Vorinstanz hat sich zu den wesentlichen Gesichtspunkten geäussert und ihren Entscheid hinreichend begründet. Die Beschwerdeführerin war denn auch ohne Weiteres in der Lage, diesen sachgerecht anzufechten.
5. Soweit die Beschwerdeführerin die offensichtlich unrichtige Feststellung des Sachverhalts durch die Vorinstanz rügt (<ref-law>), beschränkt sie sich auf appellatorische Kritik. Darauf ist nicht einzutreten (<ref-ruling> E. 2.8 S. 494 mit Hinweisen).
6. 6.1 Die Beschwerdeführerin bringt vor, das Asylverfahren habe bis zum vorinstanzlichen Entscheid zwei Jahre gedauert, was weitestgehend dem Beschwerdeverfahren zuzuschreiben sei. Dies stelle eine übermässige Verfahrensdauer dar und verletze <ref-law> sowie <ref-law>.
6.2 Gemäss <ref-law> hat jede Person im Verfahren vor Gerichts- und Verwaltungsinstanzen Anspruch auf Beurteilung innert angemessener Frist.
6.3 Nach <ref-law> trifft das BFM seinen Entscheid in der Regel innerhalb von drei Monaten nach der Gesuchstellung, wenn - wie hier - weitere Abklärungen erforderlich sind.
Die Beschwerdeführerin hat am 24. März 2010 um Asyl ersucht. Das BFM hat am 19. Mai 2010 entschieden. Es hat somit die Frist von 3 Monaten gewahrt. Eine Verletzung des Beschleunigungsgebots liegt insoweit nicht vor, was die Beschwerdeführerin auch nicht substanziiert geltend macht.
<ref-law> in der Fassung gemäss Koordinationsgesetz, wonach das Bundesamt mit besonderer Beförderlichkeit entscheidet, wenn die asylsuchende Person in Auslieferungshaft ist, kam nach dem (E. 1.2.2) Gesagten im vorliegenden Fall nicht zur Anwendung.
6.4 <ref-law> nennt Behandlungsfristen für das Bundesverwaltungsgericht. Die Frist beträgt gemäss <ref-law> in Fällen wie hier in der Regel zwei Monate.
Diese Frist hat die Vorinstanz bei Weitem nicht eingehalten. Die Beschwerde gegen den Entscheid des BFM ging bei ihr am 23. Juni 2010 ein. Erst knapp 21 Monate später fällte sie den angefochtenen Entscheid. Vom Eingang des Kostenvorschusses am 14. Juli 2010 bis zum Schreiben des Vertreters der Beschwerdeführerin vom 26. April 2011, also während gut 9 Monaten, blieb die Vorinstanz untätig. Damit hat sie das Beschleunigungsgebot verletzt.
Mit Arbeitsüberlastung kann dies nicht gerechtfertigt werden. Wenn das Bundesverwaltungsgericht nicht über die Mittel verfügt, um die Asylfälle zeitgerecht zu behandeln, muss es so ausgestattet werden, dass es in der Lage ist, dies zu tun (vgl. BGE 107 I b 160 E. 3c S. 165; <ref-ruling> E. 5c S. 198).
6.5 Die Verletzung des Beschleunigungsgebots kann nicht dazu führen, dass der Beschwerdeführerin, der - wie darzulegen sein wird - die Flüchtlingseigenschaft fehlt, in Aufhebung des angefochtenen Entscheids in der Schweiz Asyl gewährt wird. Die Verletzung des Beschleunigungsgebots ist, wie dies der bundesgerichtlichen Rechtsprechung in vergleichbaren Fällen entspricht, im vorliegenden Urteil (im Dispositiv) festzustellen. Damit und in Verbindung mit der für die Beschwerdeführerin vorteilhaften Kostenregelung (unten E. 9) wird ihr eine hinreichende Wiedergutmachung verschafft (<ref-ruling> E. 2.2 S. 121 f.; <ref-ruling> E. 2.3 S. 278; <ref-ruling> E. 3 S. 337; <ref-ruling> E. 5.3 S. 333; je mit Hinweisen).
Die Erteilung einer Aufenthaltsbewilligung durch den Kanton mit Zustimmung des BFM gemäss <ref-law> fällt schon deshalb ausser Betracht, weil sich die Beschwerdeführerin noch nicht fünf Jahre in der Schweiz aufhält.
7. 7.1 Die Beschwerdeführerin macht geltend, sie sei als Flüchtling anzuerkennen und es sei ihr folglich Asyl zu gewähren.
7.2 Gemäss <ref-law> gewährt die Schweiz Flüchtlingen auf Gesuch hin Asyl; massgebend ist dieses Gesetz.
<ref-law> umschreibt den Flüchtlingsbegriff. Danach sind Flüchtlinge Personen, die in ihrem Heimatstaat oder im Land, in dem sie zuletzt wohnten, wegen ihrer Rasse, Religion, Nationalität, Zugehörigkeit zu einer bestimmten sozialen Gruppe oder wegen ihrer politischen Anschauungen ernsthaften Nachteilen ausgesetzt sind oder begründete Furcht haben, solchen Nachteilen ausgesetzt zu werden (Abs. 1). Als ernsthafte Nachteile gelten namentlich die Gefährdung des Leibes, des Lebens oder der Freiheit sowie Massnahmen, die einen unerträglichen psychischen Druck bewirken. Den frauenspezifischen Fluchtgründen ist Rechnung zu tragen (Abs. 2).
Wer um Asyl nachsucht, muss gemäss <ref-law> die Flüchtlingseigenschaft nachweisen oder zumindest glaubhaft machen (Abs. 1). Glaubhaft gemacht ist die Flüchtlingseigenschaft, wenn die Behörde ihr Vorhandensein mit überwiegender Wahrscheinlichkeit für gegeben hält (Abs. 2). Unglaubhaft sind insbesondere Vorbringen, die in wesentlichen Punkten zu wenig begründet oder in sich widersprüchlich sind, den Tatsachen nicht entsprechen oder massgeblich auf gefälschte oder verfälschte Beweismittel abgestützt werden (Abs. 3).
7.3 Die Beschwerdeführerin macht geltend, sie und der Beschwerdeführer 1 seien in X._ von der privaten albanischen Polizei ANA - einer Art Mafia - heimgesucht, bedroht und geschlagen worden.
Die Beschwerdeführer haben widersprüchliche Aussagen zur Zahl der behaupteten Heimsuchungen durch die ANA und zur Kleidung der Täter gemacht. Angesichts dessen bestehen ernsthafte Zweifel an der Glaubhaftigkeit ihrer Aussagen. Wie es sich damit verhält, kann nach der zutreffenden Auffassung der Vorinstanz jedoch dahingestellt bleiben, da sich am Ergebnis auch dann nichts änderte, wenn ihre Angaben wahr sein sollten.
Die geltend gemachten Verfolgungsmassnahmen sind nichtstaatlicher Natur. Insoweit gilt nach der Rechtsprechung der Vorinstanz, die in Frage zu stellen für das Bundesgericht kein Anlass besteht, die sog. Schutztheorie. Danach hängt die flüchtlingsrechtliche Relevanz einer nichtstaatlichen Verfolgung vom Vorhandensein eines adäquaten Schutzes durch den Heimatstaat ab. Der Schutz vor nichtstaatlicher Verfolgung im Heimatstaat ist als ausreichend zu betrachten, wenn die betroffene Person effektiven Zugang zu einer funktionierenden und effizienten Infrastruktur hat und ihr die Inanspruchnahme eines solchen innerstaatlichen Schutzsystems individuell zumutbar ist. Dabei obliegt es der entscheidenden Behörde, die Effektivität des Schutzes im Heimatland abzuklären und zu begründen.
Der Bundesrat hat mit Beschluss vom 25. Juni 2003 Mazedonien gemäss Art. 6a Abs. 2 Bst. a AsylG als verfolgungssicheren Staat ("Safe Country") bezeichnet. Im Rahmen der periodischen Prüfung nach <ref-law> ist er darauf nicht zurückgekommen. Die Bezeichnung eines Landes als "Safe Country" begründet die Regelvermutung, dass asylrelevante staatliche Verfolgung nicht stattfindet und Schutz vor nichtstaatlicher Verfolgung gewährleistet ist.
Der Beschwerdeführerin gelingt es - wie die Vorinstanz zu Recht annimmt - nicht, diese Regelvermutung umzustossen. Damit sind die Voraussetzungen für die Zuerkennung der Flüchtlingseigenschaft nicht erfüllt und ist die Ablehnung des Asylgesuchs nicht zu beanstanden. Wie die Vorinstanz zutreffend erwägt, sind in Anbetracht der politischen Machtverhältnisse in Mazedonien die dortigen staatlichen Behörden fraglos gewillt, ihren Staatsangehörigen Schutz vor Behelligungen seitens der ANA zu gewähren, zumal es sich bei dieser um eine bewaffnete, aus dem radikalen Flügel der UÇK hervorgegangene Rebellenorganisation handelt und die mazedonischen Sicherheitskräfte mit Letzterer jahrelang in bewaffnete Konflikte verwickelt waren. Der Beschwerdeführerin wäre es damit offengestanden, den rechtsstaatlich eingerichteten Instanzenzug zu beschreiten; dies allenfalls unter Umgehung der lokalen Polizeibehörden von X._, bei denen mit der ANA möglicherweise gewisse Vernetzungen bestehen. Die geltend gemachte Bedrohung ist zudem lokal beschränkt, weshalb es der Beschwerdeführerin zuzumuten gewesen wäre, sich an einem anderen Ort in Mazedonien niederzulassen.
Beim der Beschwerdeführerin vorgeworfenen (...) handelt es sich um ein gemeinrechtliches Delikt. Es bestehen keine ernsthaften Anhaltspunkte dafür, dass dieses lediglich vorgeschoben wäre, um die Beschwerdeführerin 2 politisch zu verfolgen. Der Deliktsbetrag beläuft sich auf (...) Denar und ist daher unter Berücksichtigung der in Mazedonien gegebenen wirtschaftlichen Verhältnisse beträchtlich. Das Strafmass von (...) erscheint damit nicht als derart hoch, dass eine politisch motivierte übermässige Bestrafung ("Polit-Malus") angenommen werden müsste.
Wenn die Vorinstanz die Flüchtlingseigenschaft verneint und die Gewährung von Asyl abgelehnt hat, verletzt das demnach kein Bundesrecht. Auf die zutreffenden Erwägungen im angefochtenen Entscheid kann, was die Einzelheiten betrifft, verwiesen werden (vgl. <ref-law>).
8. 8.1 Die Beschwerdeführerin macht geltend, es bestünden jedenfalls Wegweisungshindernisse, weshalb die vorläufige Aufnahme zu verfügen sei.
8.2 Die Vorinstanz bemerkt in der Vernehmlassung, der Beschwerdegegenstand im bundesgerichtlichen Verfahren sei auf ihren Entscheid über die Anerkennung oder Nichtanerkennung der Flüchtlingseigenschaft bzw. die Asylerteilung oder Asylverweigerung beschränkt. Dies ergebe sich aus Ziffer 2.2 der Botschaft zum Koordinationsgesetz. Der Antrag auf Gewährung der vorläufigen Aufnahme "gehe daher ins Leere".
In der Botschaft wird an der von der Vorinstanz angegebenen Stelle zu Art. 83 Bst. d Ziff. 1 BGG ausgeführt, Beschwerdegegenstand sei der Entscheid des Bundesverwaltungsgerichts über die Anerkennung oder Nichtanerkennung der Flüchtlingseigenschaft bzw. die Asylerteilung oder Asylverweigerung. Weiter wird - was die Vorinstanz ausser Acht lässt - gesagt, die Beschwerdeberechtigung werde angesichts der geringen Zahl der möglichen Beschwerdefälle nicht weiter eingeschränkt, um beispielsweise die Anfechtung eines Nichteintretens- oder eines Kostenentscheids oder die Beschwerde in einem unbedeutenden Fall explizit auszuschliessen (BBl 2010 1482).
Die Darlegungen in der Botschaft stützen die Auffassung der Vorinstanz somit nicht. Wenn selbst der bundesverwaltungsgerichtliche Entscheid über die Kosten in einem Asylfall beim Bundesgericht anfechtbar sein soll, muss das erst recht gelten für die Frage, ob Wegweisungshindernisse bestehen und bejahendenfalls die vorläufige Aufnahme zu verfügen sei (in der Sache ebenso HÄBERLI, a.a.O., N 132a zu <ref-law>). Hätte der Gesetzgeber die Beschränkung der Anfechtbarkeit der Entscheide der Vorinstanz in deren Sinne vornehmen wollen, hätte er dies im Bundesgerichtsgesetz zum Ausdruck gebracht. Das hat er nicht getan.
Die Beschwerde ist daher auch im vorliegenden Punkt zulässig.
8.3 Lehnt das Bundesamt das Asylgesuch ab, so verfügt es gemäss <ref-law> in der Regel die Wegweisung aus der Schweiz und ordnet den Vollzug an; es berücksichtigt dabei den Grundsatz der Einheit der Familie (Abs. 1). Ist der Vollzug der Wegweisung nicht zulässig, nicht zumutbar oder nicht möglich, so regelt es das Anwesenheitsverhältnis nach den gesetzlichen Bestimmungen über die vorläufige Aufnahme nach dem AuG (SR 142.20; Abs. 2).
Gemäss Art. 83 AuG verfügt das BFM die vorläufige Aufnahme, wenn der Vollzug der Wegweisung nicht möglich, nicht zulässig oder nicht zumutbar ist (Abs. 1). Der Vollzug ist nicht möglich, wenn die Ausländerin oder der Ausländer weder in den Heimat- oder in den Herkunftsstaat noch in einen Drittstaat ausreisen oder dorthin gebracht werden kann (Abs. 2). Der Vollzug ist nicht zulässig, wenn völkerrechtliche Verpflichtungen der Schweiz einer Weiterreise der Ausländerin oder des Ausländers in den Heimat-, Herkunfts- oder in einen Drittstaat entgegenstehen (Abs. 3). Der Vollzug kann für Ausländerinnen oder Ausländer unzumutbar sein, wenn sie in Situationen wie Krieg, Bürgerkrieg, allgemeiner Gewalt und medizinsicher Notlage im Heimat- oder Herkunftsstaat konkret gefährdet sind (Abs. 4).
8.4 Die Beschwerdeführerin verfügt über die für die Rückkehr notwendigen Reisedokumente. Der Vollzug der Wegweisung ist daher möglich.
Dieser ist nach der zutreffenden Auffassung der Vorinstanz auch zulässig. Weder aus den Aussagen der Beschwerdeführerin noch den Akten ergeben sich Anhaltspunkte dafür, dass sie bei einer Ausschaffung in den Heimatstaat dort mit beachtlicher Wahrscheinlichkeit einer völkerrechtlich verbotenen unmenschlichen Behandlung ausgesetzt wäre. Auch die allgemeine Menschenrechtslage in Mazedonien lässt den Vollzug der Wegweisung nicht als unzulässig erscheinen, da dieser Staat als "Safe Country" gilt.
Nicht zu beanstanden ist der angefochtene Entscheid ebenso, soweit die Vorinstanz zum Schluss kommt, der Vollzug der Wegweisung sei zumutbar. Das Vorbringen der Beschwerdeführerin, wonach sie bei einer Rückkehr eine klägliche Existenz in Not und Armut fristen müsste, überzeugt nicht, konnten die Beschwerdeführer doch in ihrem Heimatstaat innert 24 Stunden die Summe von 5'000 Euro für die Ausstellung von Pässen erhältlich machen. Zu den geltend gemachten psychischen Problemen der Beschwerdeführerin ist Folgendes zu bemerken: In Mazedonien besteht eine obligatorische Krankenversicherung, die auf dem Prinzip der Universalität (Deckung aller Bürger) beruht. Damit ist davon auszugehen, dass eine medizinische Versorgung - unabhängig von den finanziellen Verhältnissen des Erkrankten - in ganz Mazedonien flächendeckend zugänglich ist. In der von X._ etwa (...) km entfernten Hauptstadt Skopje steht zudem die Infrastruktur für die Behandlung einer psychischen Beeinträchtigung, wie sie bei der Beschwerdeführerin diagnostiziert worden ist, zur Verfügung. Eine medizinische Notlage im Sinne von Art. 83 Abs. 4 AuG kann daher nicht angenommen werden.
Ist der Vollzug der Wegweisung demnach möglich, zulässig und zumutbar, ist er zu bestätigen. Die vorläufige Aufnahme fällt ausser Betracht. Auf die ausführlichen Erwägungen im angefochtenen Entscheid kann auch insoweit verwiesen werden.
9. Nach dem Gesagten ist die Beschwerde, soweit darauf eingetreten werden kann, teilweise gutzuheissen und festzustellen, dass die Vorinstanz das Beschleunigungsgebot verletzt hat. Im Übrigen ist die Beschwerde abzuweisen.
Die Beschwerdeführer unterliegen zur Hauptsache. Unter den gegebenen Umständen (oben E. 6.5) werden jedoch keine Kosten erhoben (<ref-law>). Die Eidgenossenschaft hat den Vertretern der Beschwerdeführer wegen ihres teilweisen Obsiegens eine Entschädigung zu bezahlen (Art. 68 Abs. 1 und 2 BGG). Diese wird auf insgesamt Fr. 3'000.-- (inkl. Mehrwertsteuer) festgesetzt und den Vertretern je zur Hälfte zugesprochen. Dass es sich bei Niklaus Rüst offenbar um keinen Rechtsanwalt handelt, steht dem nicht entgegen (Art. 9 des Regelements vom 31. März 2006 über die Parteientschädigung und die Entschädigung für die amtliche Vertretung im Verfahren vor dem Bundesgericht; SR 173.110.210.3). Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung ist damit hinfällig.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird, soweit darauf eingetreten werden kann, teilweise gutgeheissen und es wird festgestellt, dass das Bundesverwaltungsgericht das Beschleunigungsgebot verletzt hat. Im Übrigen wird die Beschwerde abgewiesen.
2. Es werden keine Gerichtskosten erhoben.
3. Die Eidgenossenschaft (Bundesamt für Migration) hat den Vertretern der Beschwerdeführer, Rechtsanwalt Peter Kreis und Niklaus Rüst, eine Entschädigung von je Fr. 1'500.-- zu bezahlen.
4. Dieses Urteil wird den Beschwerdeführern, dem Bundesamt für Migration, dem Bundesverwaltungsgericht, Abteilung V, und dem Bundesamt für Justiz, Fachbereich Auslieferung, schriftlich mitgeteilt.
Lausanne, 15. Oktober 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Härri