Sachverhalt:
A. A.a Am 23. April 2008 wurde über die A._ AG in B._ der Konkurs eröffnet. Zur Konkursmasse gehörten die Grundstücke Grundbuch B._ Nr. xxxx und Nr. yyyy. An der internen Steigerung vom 17. März 2009 wurden die Liegenschaften X._ und Y._ zum Preis von Fr. 1'105'000.-- zugeschlagen. Am 24. März 2009 unterzeichneten das Konkursamt und die Käufer die entsprechende Freihandverkaufsverfügung. Noch vor der internen Steigerung waren die Käufer Grundpfandgläubiger hinsichtlich der beiden Liegenschaften geworden.
Ziffer 5 der Freihandverkaufsverfügung hat den Titel "Kosten" und lautet wie folgt:
"Die Kosten und Gebühren des Grundbuchamtes mit Einschluss der Handänderungssteuer übernimmt die Kaufspartei. Das Grundbuchamt stellt dafür separat Rechnung. Sämtliche Kosten des Kantonalen Konkursamtes werden vorweg aus dem Mietzinserlös bezahlt.
Sollte dieser nicht zur Deckung der Gebühren und Auslagen des Kantonalen Konkursamtes ausreichen, so verpflichtet sich die Kaufspartei mit Unterzeichnung der vorliegenden Verfügung, dem Konkursamt auf Verlangen hin den Restbetrag innerhalb von 10 Tagen einzuzahlen."
A.b Die Eidgenössische Steuerverwaltung (ESTV), Hauptabteilung Mehrwertsteuer, stellte der A._ AG am 31. Juli 2009 eine Mehrwertsteuerforderung von Fr. 60'000.-- in Rechnung. Das Konkursamt bezahlte den Betrag am 23. Oktober 2009.
A.c Am 23. Dezember 2009 rechnete das Konkursamt über die Verwertung der beiden Grundstücke ab. Dabei überwälzte es die Mehrwertsteuer von Fr. 60'000.-- auf X._ und Y._ und stellte ihnen den Saldo von Fr. 46'390.95 in Rechnung. Mit Eingaben vom 29. Dezember 2009, 4. Januar 2010 und 6. Januar 2010 erhoben X._ und Y._ Beschwerde gegen die Kostenrechnung. Sie wandten sich gegen die Überwälzung der Mehrwertsteuer.
B. Die Aufsichtsbehörde für Schuldbetreibung und Konkurs des Kantons Solothurn hiess die Beschwerde mit Urteil vom 12. April 2011 gut, hob die Kostenrechnung vom 23. Dezember 2009 auf und wies die Sache zu neuem Entscheid an das Konkursamt zurück.
C. Am 4. Mai 2011 hat das Konkursamt Beschwerde in Zivilsachen erhoben. Es beantragt die Aufhebung des angefochtenen Urteils der Aufsichtsbehörde. X._ und Y._ (Beschwerdegegner) seien zur Bezahlung der Kostenrechnung vom 23. Dezember 2009 im Betrag von Fr. 46'390.95 zuzüglich 5 % Zins seit 24. Januar 2010 zu verurteilen.
Die Beschwerdegegner und die Aufsichtsbehörde ersuchen um Abweisung der Beschwerde, soweit darauf einzutreten sei.

Erwägungen:
1. Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-ruling> E. 1 S. 216 mit Hinweisen).
1.1 Gemäss bundesgerichtlicher Rechtsprechung ist ein Betreibungs- und Konkursamt zur Beschwerde legitimiert, wenn es als Organ des Kantons handelt und fiskalische Interessen desselben geltend macht, wenn es sich gegen die konkrete Anwendung der Gebührenverordnung (GebV SchKG [SR 281.35]) zur Wehr setzt oder wenn es Interessen der Konkursmasse wahrt (<ref-ruling> E. 1.3 S. 138 mit Hinweisen; Urteil 5A_79/2010 vom 7. Juni 2010 E. 1.2, in: Pra 100/2011 Nr. 30 S. 205). Das Amt hat jedoch keine Beschwerdeberechtigung, wenn es bloss seine Auffassung gegenüber derjenigen der Aufsichtsbehörde durchgesetzt sehen möchte oder wenn es sich gegen eine Anordnung der Aufsichtsbehörde wehren will, welche diese gestützt auf ihre Aufsichtsfunktion erlassen hat (Urteile 5A_79/2010 vom 7. Juni 2010 E. 1.3, in: Pra 100/2011 Nr. 30 S. 205; 5A_238/2011 vom 5. Juli 2011 E. 3.2; je mit Hinweisen). Eine allgemeine Behördenbeschwerde gibt es in diesem Bereich nicht.
1.2 Die Beschwerde ist gemäss Art. 42 Abs. 1 und Abs. 2 BGG hinreichend zu begründen. Der Beschwerdeführer hat insbesondere darzulegen, dass die gesetzlichen Legitimationsvoraussetzungen gegeben sind. Soweit diese nicht ohne weiteres ersichtlich sind, ist es nicht Aufgabe des Bundesgerichts, anhand der Akten oder weiterer, noch beizuziehender Unterlagen nachzuforschen, ob und inwiefern der Beschwerdeführer zur Beschwerde zuzulassen ist (<ref-ruling> E. 1 S. 356 mit Hinweis).
Das beschwerdeführende Amt äussert sich einzig zu Art. 76 Abs. 1 lit. a BGG ausdrücklich, nicht aber zu den soeben dargestellten Voraussetzungen seiner Legitimation (oben E. 1.1). Sinngemäss macht es allerdings geltend, Interessen der Masse wahrzunehmen (vgl. Urteil 7B.9/2005 vom 3. Mai 2005 E. 1). Es strebt nämlich an, die Mehrwertsteuer als Teil der Verwertungskosten auf die Beschwerdegegner abzuwälzen und es behauptet implizit durch die Berufung auf <ref-ruling>, es handle sich bei der Mehrwertsteuerforderung um eine Massaschuld (Ziff. 2.2 der Beschwerde). Insoweit genügt es den Begründungsanforderungen und dem Amt ist die Beschwerdelegitimation zuzuerkennen.
1.3 Der angefochtene Entscheid weist die Angelegenheit an das Konkursamt zurück. Er ist somit an sich ein Zwischenentscheid gemäss Art. 93 BGG (<ref-ruling> E. 1.2 S. 138). Wenn der Rückweisungsentscheid allerdings präzise Anweisungen an die untere Instanz enthält (<ref-ruling> E. 1.2 S. 138 mit Hinweis) und ihr kein Entscheidungsspielraum mehr verbleibt, sondern sie einzig das oberinstanzlich Angeordnete umzusetzen hat (<ref-ruling> E. 1.1 S. 143 mit Hinweisen), handelt es sich um einen Endentscheid (Art. 90 BGG; <ref-ruling> E. 1.3 S. 127 mit Hinweisen).
Vorliegend ist die Rückweisung einzig zum Zweck erfolgt, dass das Konkursamt eine neue Abrechnung ohne die strittige Mehrwertsteuerforderung erstelle. Andere Aspekte der Abrechnung waren nicht streitig. Da dem Konkursamt bei der Umsetzung des Rückweisungsentscheids kein Spielraum bleibt, kann er als Endentscheid vor Bundesgericht angefochten werden. Die Zulässigkeit der Beschwerde ergibt sich aus dem angefochtenen Urteil. Dass das beschwerdeführende Amt auf diese Zulässigkeitsvoraussetzung nicht eingegangen ist, schadet ihm demnach nicht.
1.4 Die übrigen Eintretensvoraussetzungen sind ebenfalls erfüllt (Art. 74 Abs. 2 lit. c, Art. 75, Art. 100 Abs. 2 lit. a i.V.m. Art. 46 Abs. 1 lit. a BGG).
2. Die Aufsichtsbehörde hat die Überwälzung der Mehrwertsteuer auf die Beschwerdegegner aus mehreren Gründen für unzulässig erachtet. Die Mehrwertsteuer stelle weder eine Gebühr noch eine Auslage im Sinne von Ziffer 5 der Freihandverkaufsverfügung dar, so dass für die Überwälzung keine Rechtsgrundlage bestehe (dazu unten E. 3.3). Mehrwertsteuerforderungen seien des Weiteren als Verwertungskosten zu qualifizieren, die vorab aus dem Erlös der betreffenden Grundstücke zu decken seien. Vorliegend gebe es keinen Erlös, weil die Beschwerdegegner die Grundpfandforderungen von den ursprünglichen Grundpfandgläubigern übernommen und den Kaufpreis mit der Grundpfandforderung verrechnet hätten (dazu unten E. 3.2). Schliesslich betreffe die fragliche Mehrwertsteuerrechnung das zweite Quartal 2008 und stehe deshalb in keinem direkten Zusammenhang mit dem Freihandverkauf vom 24. März 2009 (dazu unten E. 3.1).
3. 3.1 Die Ansicht, dass die Mehrwertsteuerrechnung keinen Zusammenhang mit dem Freihandverkauf habe, trifft nicht zu. In der Rechnung der ESTV vom 31. Juli 2009 steht zwar, sie betreffe die Steuerperiode 2. Quartal 2008. Das beschwerdeführende Amt erklärt dies damit, das Datum der Konkurseröffnung über die A._ AG (23. April 2008) sei für die Mehrwertsteuerbehörde für alle Abrechnungen im Zusammenhang mit der Liquidation massgeblich und Vorsteuern würden bis und mit diesem Datum berücksichtigt. Wie es sich mit der Praxis der ESTV genau verhält, braucht nicht geklärt zu werden. Jedenfalls bezieht sich die Rechnung ausdrücklich auf den Freihandverkauf von Liegenschaften der A._ AG. Dass dieser Verkauf im Jahre 2009 stattgefunden hat, ergibt sich aus der Berechnung der Eigenverbrauchssteuer für den Liegenschaftsverkauf selber: Die ESTV führt aus, die Vorsteuern seien im Jahre 2003 geltend gemacht worden, und sie nimmt auf dem Betrag dieser Vorsteuern eine Abschreibung für die Zeitdauer von sechs Jahren vor. Schliesslich bezieht sich die ESTV in der Rechnung ausdrücklich auf ein Schreiben vom 29. Juli 2009. Damit meint sie offensichtlich die Anfrage des Konkursamts von diesem Datum, mit der es die mehrwertsteuerrechtliche Behandlung des Freihandverkaufs der beiden fraglichen Liegenschaften abklären wollte. Die Mehrwertsteuerrechnung vom 31. Juli 2009 steht demnach in Zusammenhang mit der Veräusserung der beiden Liegenschaften durch das Konkursamt am 24. März 2009. Dies wird im Übrigen auch von den Beschwerdegegnern in ihrer Vernehmlassung anerkannt. Ob die Mehrwertsteuerabrechnung inhaltlich richtig ist, kann und muss hier nicht beurteilt werden. Sie ist unangefochten geblieben.
3.2 Gemäss <ref-ruling> ist die Mehrwertsteuer, die bei der Verwertung eines Grundstücks anfällt, aus dem Erlös des betreffenden Grundstücks vorab zu decken. Die Mehrwertsteuerforderung gehört zu den Verwertungskosten gemäss Art. 262 Abs. 2 SchKG. Der Erlös aus der Verwertung der Grundstücke entspricht dem Verkaufspreis. Dass die Kaufpreisforderung durch Verrechnung mit der Grundpfandschuld getilgt wurde, ändert daran nichts. Auch dies anerkennen die Beschwerdegegner in ihrer Vernehmlassung.
3.3 Ob für die Überwälzung der Mehrwertsteuer auf die Beschwerdegegner eine genügende Grundlage besteht, lässt sich derzeit noch nicht sagen. Die Freihandverkaufsverfügung ist eine zustimmungsbedürftige Verfügung und insoweit ein zweiseitiges Rechtsgeschäft. Wenngleich es sich nicht um einen Vertrag handelt, sind hinsichtlich Rechtswirksamkeit weitgehend die privatrechtlichen Regeln über die Willenserklärungen im Allgemeinen und jene über den Vertragsschluss im Besonderen analog anzuwenden (Urteil 7B.66/2003 vom 11. Juni 2003 E. 2.2 mit Hinweisen). Demgemäss ist die Freihandverkaufsverfügung grundsätzlich nach dem Vertrauensprinzip auszulegen. Um zu bestimmen, welche Bedeutung der Erwerber der Verfügung beilegen durfte und musste, sind namentlich die Vorverhandlungen zu berücksichtigen (FRANCO LORANDI, Der Freihandverkauf im schweizerischen Schuldbetreibungs- und Konkursrecht, 1993, S. 68). Die Beschwerdegegner machten bereits in ihrer Beschwerde an die Aufsichtsbehörde geltend und halten vor Bundesgericht daran fest, sich anlässlich der Verkaufsverhandlungen nach den zusätzlichen Kosten erkundigt zu haben. Die zuständige Sachbearbeiterin, Notarin C._, habe auf diverse Kosten hingewiesen (insbesondere Grundbuchgebühren und Handänderungssteuer). Von der Mehrwertsteuer sei jedoch nie die Rede gewesen. Die Sachbearbeiterin habe sich am Telefon gegenüber den Beschwerdegegnern nach Zustellung der Veranlagungsverfügung selber von der Mehrwertsteuerforderung überrascht gezeigt und diese für unberechtigt gehalten. Die Vorinstanz hat diese Behauptungen noch nicht näher untersucht. Sie könnten sowohl für die Auslegung der umstrittenen Ziffer 5 der Freihandverkaufsverfügung wie auch im Hinblick auf Willensmängel und den allfälligen Vertrauensschutz in behördliche Zusicherungen relevant sein. Der angefochtene Entscheid ist deshalb aufzuheben und die Angelegenheit zu neuer Beurteilung in tatsächlicher und rechtlicher Hinsicht an die Vorinstanz zurückzuweisen.
4. Bei diesem Verfahrensausgang rechtfertigt es sich, die Gerichtskosten hälftig dem beschwerdeführenden Amt einerseits und den beiden Beschwerdegegnern andererseits aufzuerlegen (Art. 66 Abs. 1 BGG). Parteientschädigungen sind nicht zu sprechen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen und das Urteil der Aufsichtsbehörde für Schuldbetreibung und Konkurs des Kantons Solothurn vom 12. April 2011 aufgehoben. Die Angelegenheit wird zur Behandlung im Sinne der Erwägungen an die Aufsichtsbehörde zurückgewiesen.
2. Die Gerichtskosten von insgesamt Fr. 1'000.-- werden zur Hälfte dem beschwerdeführenden Amt einerseits und den Beschwerdegegnern andererseits auferlegt. Die Beschwerdegegner haften für ihren Anteil von Fr. 500.-- solidarisch.
3. Es werden keine Parteientschädigungen gesprochen.
4. Dieses Urteil wird den Parteien und der Aufsichtsbehörde für Schuldbetreibung und Konkurs des Kantons Solothurn schriftlich mitgeteilt.
Lausanne, 16. November 2011
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Hohl
Der Gerichtsschreiber: Zingg