Wo sind sie gespeichert?
In der collections.db!

Meine Collections/meine collections.db ist weg, wie bekomme ich sie wieder?
Du bekommst sie nicht wieder. Deine einzige Chance besteht darin, dass sie noch im Papierkorb liegt oder unter einem modifizierten Namen im osu!-Ordner, aber das ist erfahrungsgemäß in der Mehrheit der Fälle nicht der Fall. Deshalb: Sichern, sichern, sichern! Dann hast du im Zweifelsfall ein paar Tage, ein paar Wochen oder wenn es dumm gelaufen ist, wenige Monate verloren. Davon kann man sich erholen, vom Verlust der Collections aus 2 Jahren in der Regel nicht.

Wie kann ich die Datei sichern?
Kopiere sie an einen sicheren Ort und benenne sie so, dass du sie wiederfindest und in etwa einschätzen kannst, wieviele Daten du wirklich verloren hast.

Ein unsicherer Ort ist im Regelfall auch vollkommen in Ordnung, es reicht sogar, sie im osu!-Ordner zu lassen.

Wie oft soll ich die Datei sichern?
Diese Datei ist selbst bei vielen Collections mit vielen Maps nur sehr klein, du kannst sie wöchentlich oder sogar täglich sichern, ohne dir Gedanken um Platzprobleme machen zu müssen.
Es kann sich lohnen eine automatische Sicherung für diese Datei einzurichten.

Wo sind sie gespeichert?
In der osu!.db. Neben Standard-Informationen wird hier auch gespeichert, ob du die Beatmap schon gespielt hast und auch wann du sie gespielt hast.

osu! sagt mir meine Datenbank sei korrupt, weil manuell etwas daran geändert worden sei. Was soll ich tun?
osu! ist leicht sehr gekränkt, wenn man schon nur zu Mapping-Zwecken ein bisschen in einem Beatmap-Ordner herumfuhrwerkt oder vor dem Bildschirm Samba tanzt. Diese Warnung kannst du in aller Regel ignorieren, sofern du keine anderen komischen Phänomene in der Songauswahl sichtest.

Ich habe in der Tat komische Phänomene in der Songauswahl. Was jetzt?
Deine osu!-Datenbank ist wirklich korrupt. Leider passiert das bei dieser Datenbank verhältnismäßig häufig im Vergleich zu den anderen.
Du kannst zunächst versuchen mit F5 in der Songauswahl alle Beatmaps neu einzulesen. Dabei gehen die Daten, wann du was gespielt hast, nicht verloren.
Wenn das aber nicht hilft, musst du osu! schließen, die osu!.db aus dem osu!-Ordner entfernen (am besten verschiebst du sie erstmal woanders hin, falls du sie doch noch brauchst) und osu! dann neustarten. Daraufhin baut osu! die Datenbank nochmal komplett neu auf. Die Daten, wann du was gespielt hast, sind dann leider weg. Das ist zwar ärgerlich, andererseits sind dies nun nicht die allerwichtigsten.

Lohnt es sich, diese Datei zu sichern?
Eher nicht. Dafür gibt es mehrere Gründe. Zum einen werden zu den Maps, die du in der Zeit nach einem Backup gespielt hast, genau die Informationen, die du sichern wolltest auch fehlen. Dem könnte man entgegenwirken, indem man wirklich oft Sicherungen erstellt, aber die osu!.db ist verhältnismäßig groß (64MB bei 100GB großem Song-Ordner), so dass Platz schnell zu einem Problem wird, wenn man seine Sicherungen nicht ordentlich pflegt. Und an der Stelle stellt sich die Frage von Aufwand gegenüber Gewinn - es sind halt gespielte Maps nicht mehr als gespielt markiert...die Maps sind noch da, die Scores sind noch da, am Ende läuft alles auf die Farbe des Beatmapsets in der Songauswahl und die Sortierung nach "Zuletzt gespielt" hinaus. Wenn du schon ein Sicherungssystem in Gang hast, das sowas für dich automatisch erledigen kann, mach das unbedingt, aber andernfalls würde ich eher davon abraten.

Wo sind sie gespeichert?
Im osu!-Ordner gibt es einen versteckten Ordner namens "Data".
Da kommst du entweder rein, indem du versteckte Ordner in deiner Systemsteuerung sichtbar machst, oder noch einfacher, indem du oben in der Adresszeile vom Explorer "\Data" hinten anfügst (ohne die "") und Enter drückst.
In diesem Data-Folder gibt es nun einen Ordner namens "r". In dem sind alle deine Scores und Replays in Form kryptisch aussehender Dateien abgespeichert:

Zusätzlich gibt es im normalen osu!-Verzeichnis eine Datei scores.db. In dieser sind alle deine Scores nochmal aufgelistet, sie enthält aber keine Replay-Informationen.

Meine lokalen Scores laden nicht, was soll ich tun?
Schließe osu!, schieb die scores.db aus deinem osu!-Ordner und starte osu! neu. Wenn du dann immer noch nichts siehst, guck im Data\r-Ordner nach, wie alt die älteste Datei dort ist. Wenn Scores oder Replays verschwinden, tun sie das meist zeitlich von hinten. So kannst du abschätzen, ob etwas verloren gegangen sind und wenn ja wieviel.
Wenn an dieser Stelle schon etwas fehlt, ist es zu spät.

Einige meiner Replays sind verschwunden!
Ja, oft verschwinden die Replays alleine aber die Scores bleiben da. Verrückt. Leider gibt es hierfür keine brauchbare Erklärung und da es zum einen nicht so häufig vorkommt und zum anderen die meisten Leute sich ihre eigenen älteren Replays nicht allzuhäufig anschauen, fällt es oft erst auf, wenn der eigentliche Verlust schon Wochen und Monate zurückliegt (da wie schon angesprochen die ältesten Replays oft zuerst verschwinden).

Wie kann ich meine Scores und Replays sichern?
Indem du den Data\r-Ordner kopierst. Da es viele Einzeldateien sind, die zusammen ganz schön was an Größe hermachen (mein r-Ordner ist 1GB groß), kann es sich durchaus lohnen den ganzen Ordner zu komprimieren. Dazu machst du einen Rechtsklick auf den Ordner, wählst "Senden an" und dann "ZIP-komprimierter Ordner". Den so komprimierten Ordner an einem sicheren Ort ablegen.

Lohnt es sich, die scores.db mitzusichern?
Njein. Wenn du den Data\r-Ordner sowieso sicherst, macht es eigentlich keinen Sinn mehr. Hier sind noch einige Header-Daten zu den Scores vorhanden, und ein Backup der scores.db ist besser als gar nichts, aber wenn man die Wahl hat, sollte man stattdessen den Data\r-Ordner sichern.

Wie oft sollte ich den Data\r-Ordner sichern?
So oft wie du möchtest. Erfahrungsgemäß geht hier nicht allzu häufig etwas kaputt und es gibt jahrealte Installationen, wo nie etwas weggekommen ist. Bei mir hat nach 2 Jahren zum ersten mal etwas gefehlt. Aufgrund der Größe würde ich eine Sicherung monatlich oder quartalsweise empfehlen, je nachdem, was dein Plattenspeicher so hergibt. Oder eben automatisiert sichern.

Warum verschwinden die Scores und Replays manchmal überhaupt?
Eine sehr gute Frage und leider eine, auf die wir keine Antwort kennen

Strg+C und Strg+V sind der Weg!
Alles was osu! fehlt, lädt es beim ersten Start nach. Es gibt keinen Grund tatsächlich eine Neuinstallation zu fahren und einzelne Dateien separat zu kopieren. Einfach den ganzen Ordner nehmen und rüberpacken. Falls du dir nicht sicher bist, wo die Sachen gespeichert sind, osu! hat in den Optionen einen Knopf "osu! Ordner öffnen".
Danach gibt es nur noch eine einzige kleine Änderung die darin besteht, deinen alten Benutzernamen in dieser Datei in deinen neuen Benutzernamen zu ändern, wenn er denn nicht sowieso gleich ist:

NEIN. TUS NICHT.
Grundsätzlich lassen sich in osu! 99% aller Probleme NICHT durch eine Neuinstallation lösen. Wende dich bei einem technischen Problem zuerst ans Help-Forum oder falls Englisch dir nicht liegt, mach hier im deutschsprachigen Bereich ein Thema dazu auf.
Durch eine Deinstallation von osu! werden alle deine Maps, Scores, Replays, Collections, wirklich alles gelöscht. Sollte dieser Schritt also wirklich nötig sein (wie schon angemerkt, fast nie), sorg dafür dass du alle deine osu!-Daten gesichert hast. Im Zweifel einfach den kompletten Ordner nochmal woanders hinkopieren.