Sachverhalt:
A. Auf Betreibungsbegehren der Y._ AG hin stellte das Betreibungsamt Dorneck am 12. Dezember 2011 einen Zahlungsbefehl (Betreibung Nr. xxx) gegen X._ (Adresse: A._-strasse xx, xxxx B._, Kanton Solothurn) aus. Da X._ die Post an ihre Tochter Z._ umgeleitet hatte, konnte die Post den Zahlungsbefehl in B._ nicht zustellen. Dieser wurde am 2. Februar 2012 rechtshilfeweise durch das Betreibungsamt Basel-Stadt zugestellt und von Z._ entgegengenommen.
Am 7. Februar 2012 erhob X._ Beschwerde gegen den Zahlungsbefehl und machte geltend, sie habe keinen Wohnsitz mehr in B._, sondern dieser befinde sich in C._ (Frankreich). Ihre Tochter sei zudem nicht berechtigt gewesen, den Zahlungsbefehl entgegenzunehmen.
Mit Urteil vom 29. März 2012 wies die Aufsichtsbehörde für Schuldbetreibung und Konkurs des Kantons Solothurn die Beschwerde ab. Unter Bezugnahme auf <ref-law> und <ref-law> erwog die Aufsichtsbehörde, die Schriftenhinterlegung bilde ein Indiz für die Wohnsitzbestimmung. X._ verweise als Beweis für ihren Wohnsitzwechsel einzig auf einen Eheschutzentscheid vom 18. November 2011. Sie habe sich aber trotz der in diesem Entscheid genannten Adresse in Frankreich bis heute in B._ nicht abgemeldet und sie lasse ihre Post von B._ zu ihrer Tochter nach Basel umleiten. Ihr Verhalten spreche für die Aufrechterhaltung des Wohnsitzes in B._ und einen nur vorübergehenden Aufenthalt in Frankreich. Der Umleitungsauftrag wäre überflüssig gewesen, wenn sie sich im Zusammenhang mit den ehelichen Problemen definitiv von B._ hätte abwenden wollen.
B. Am 25. April 2012 hat X._ (Beschwerdeführerin) Beschwerde an das Bundesgericht erhoben. Sie verlangt die Aufhebung des Urteils der Aufsichtsbehörde. Zudem ersucht sie um aufschiebende Wirkung.
Die Y._ AG (Beschwerdegegnerin) hat sich dem Gesuch um aufschiebende Wirkung widersetzt und die Aufsichtsbehörde sowie das Betreibungsamt Dorneck haben auf Stellungnahme verzichtet. Mit Präsidialverfügung vom 24. Mai 2012 ist der Beschwerde aufschiebende Wirkung zuerkannt worden.
Das Bundesgericht hat die Akten beigezogen, in der Sache aber keine Vernehmlassungen eingeholt.

Erwägungen:
1. Entscheide in Schuldbetreibungs- und Konkurssachen unterliegen der Beschwerde in Zivilsachen (<ref-law>). Beschwerdeentscheide der kantonalen Aufsichtsbehörden über Verfügungen der Vollstreckungsorgane gemäss <ref-law> - wie die Zustellung des Zahlungsbefehls - sind Endentscheide im Sinne von <ref-law> (<ref-ruling> E. 1.2 S. 351). Die Beschwerde in Zivilsachen ist grundsätzlich zulässig.
Mit Beschwerde in Zivilsachen kann u.a. die Verletzung von Bundesrecht gerügt werden (<ref-law>). Die Beschwerde ist zu begründen (<ref-law>). Nach <ref-law> ist in der Begründung in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Dies setzt voraus, dass sich der Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheids auseinandersetzt (<ref-ruling> E. 2.1 S. 245 f.; <ref-ruling> E. 3.3 S. 60). Im Weiteren legt das Bundesgericht seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Seine Feststellung kann nur gerügt werden, wenn sie offensichtlich unrichtig - d.h. willkürlich (<ref-ruling> E. 1.5 S. 130 mit Hinweis) - ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und die Behebung des Mangels für den Verfahrensausgang entscheidend sein kann (<ref-law>). Inwiefern diese Voraussetzungen erfüllt sein sollen, muss in der Beschwerde substanziiert begründet werden (<ref-ruling> E. 4.2 S. 234; <ref-ruling> E. 5.1 S. 356). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
2. 2.1 Die Beschwerdeführerin bringt vor, durch ihren Ehemann aus dem ehelichen Domizil in B._ verwiesen worden zu sein und seit dem 15. November 2008 in Frankreich zu leben. Sie halte sich dauernd in Frankreich auf, halte dort Tiere, die ihre Anwesenheit erforderten, verfüge über keine Wohnmöglichkeit mehr in der Schweiz und die Hälfte der Liegenschaft, die sie in Frankreich bewohne, gehöre ihr. Daraus ergebe sich die Absicht dauernden Verbleibens in Frankreich. In der Zwischenzeit habe sie sich in B._ abgemeldet und ihre Schriften abgeholt. Die Hinterlegung der Papiere in B._ und das postalische Zustelldomizil seien bloss aus Praktikabilitätsgründen aufrechterhalten worden. Bis zur Beendigung der ehelichen Auseinandersetzung habe sie den Anschluss an die schweizerischen Sozialversicherungen nicht verlieren wollen.
2.2 Die Beschwerdeführerin begründet ihre Beschwerde weitestgehend mit Sachverhaltsbehauptungen, die im angefochtenen Urteil keine Stütze finden und die zudem erstmals vor Bundesgericht vorgetragen werden. Gemäss <ref-law> sind jedoch neue Tatsachen unzulässig, die bereits der Vorinstanz hätten vorgelegt werden können (<ref-ruling> E. 4.4.3 S. 129). Dies trifft insbesondere für die angeblichen Verhältnisse der Beschwerdeführerin in Frankreich zu. Neu sind auch ihre Ausführungen zu den Absichten, die sie mit der Aufrechterhaltung der Schriftenhinterlegung in B._ verfolgt habe. Unzulässig ist ferner die Berufung auf Tatsachen, die erst nach dem angefochtenen Urteil eingetreten sind (<ref-ruling> E. 2.1 S. 343 f.). Die behauptete Abmeldung in B._ ist offenbar erst nach dem angefochtenen Urteil erfolgt, so dass sie vor Bundesgericht nicht vorgebracht werden kann. Insgesamt kann auf die Beschwerde somit nicht eingetreten werden.
3. Bei diesem Ausgang des Verfahrens trägt die Beschwerdeführerin die Gerichtskosten (<ref-law>). Hingegen schuldet sie keine Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde wird nicht eingetreten.
2. Die Gerichtskosten von Fr. 700.-- werden der Beschwerdeführerin auferlegt.
3. Dieses Urteil wird den Verfahrensbeteiligten und der Aufsichtsbehörde für Schuldbetreibung und Konkurs des Kantons Solothurn schriftlich mitgeteilt.
Lausanne, 11. Juni 2012
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Escher
Der Gerichtsschreiber: Zingg