Sachverhalt:
A. Der türkische Staatsangehörige X._ (geb. 1972) reiste im April 1988 als knapp Sechzehnjähriger im Rahmen des Familiennachzugs in die Schweiz und erhielt die Niederlassungsbewilligung im Kanton Aargau. Am 11. März 2003 entmündigte ihn das Bezirksgericht A._ (Kanton Aargau) gestützt auf Art. 370 ZGB. Seine im Jahre 1994 in der Türkei mit einer Landsfrau geschlossene Ehe wurde mit Urteil vom 29. September 2005 geschieden. Aus dieser Ehe sind zwei Kinder hervorgegangen (geb. 1997 und 2000), die unter die elterliche Sorge der Mutter gestellt wurden.
Im Januar 2007 meldete sich X._ von B._ (AG) nach C._ (SO) ab. Am 29. März 2007 beantragte er die Genehmigung eines Wechsels vom Kanton Aargau in den Kanton Solothurn. Mit Verfügung vom 14. Juli 2008 wies das Departement des Innern des Kantons Solothurn - Abteilung Ausländerfragen - das Gesuch ab und forderte ihn auf, das Gebiet des Kantons Solothurn zu verlassen und sich bei der Einwohnerkontrolle C._ abzumelden. Die beim Verwaltungsgericht des Kantons Solothurn erhobene Beschwerde blieb erfolglos.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 10. Dezember 2008 beantragt X._, das Urteil des Verwaltungsgerichts vom 3. November 2008 aufzuheben, den Kantonswechsel zu bewilligen und die zuständigen Behörden anzuweisen, ihm die Niederlassungsbewilligung für den Kanton Solothurn zu erteilen.
Das Verwaltungsgericht stellt den Antrag, die Beschwerde abzuweisen, soweit darauf eingetreten werden könne. Das Departement des Innern des Kantons Solothurn sowie das Bundesamt für Migration beantragen die Abweisung der Beschwerde.
C. Mit Verfügung vom 16. Dezember 2008 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt.

Erwägungen:
1. Gemäss Art. 126 AuG (SR 142.20) ist der Antrag auf Kantonswechsel - abgesehen vom Verfahren - nach dem bis zum 31. Dezember 2007 geltenden Ausländerrecht zu beurteilen, da er vor diesem Datum eingereicht worden ist. Das insoweit anzuwendende Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121) vermittelt - im Gegensatz zum neuen Art. 37 AuG - keinen Anspruch auf Kantonswechsel. Der Beschwerdeführer kann einen solchen Anspruch allerdings aus dem mit der Türkei abgeschlossenen Niederlassungsabkommen vom 13. Dezember 1930 (SR 0.142.117.632) ableiten (vgl. <ref-ruling> E. 2b S. 180; <ref-ruling> E. 2b S. 149 f.).
2. Das Bundesgericht prüft die Zulässigkeit der Beschwerden von Amtes wegen (Art. 29 Abs. 1 BGG; <ref-ruling> E. 1 Ingress S. 31, 94 E. 1 S. 96). Nach der bis zum 31. Dezember 2007 geltenden Rechtslage war die Beschwerde in öffentlich-rechtlichen Angelegenheiten bzw. die Verwaltungsgerichtsbeschwerde an das Bundesgericht gegen die Verweigerung eines Kantonswechsels zulässig, wenn ein Anspruch auf Wohnsitznahme in einem neuen Kanton bestand (vgl. zum BGG: Urteil 2C_24/2007 vom 10. Juli 2007 E. 1.2; zum OG: <ref-ruling> E. 1 S. 67; <ref-ruling> E. 2 S. 179 ff.).
Gemäss der neu eingeführten Ziff. 6 von Art. 83 lit. c BGG, die seit dem 1. Januar 2008 zur Anwendung kommt (AS 2006 5600 und 5608 in Verbindung mit dem Bundesratsbeschluss vom 24. Oktober 2007, AS 2007 5489), ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten unzulässig auf dem Gebiet des Ausländerrechts betreffend den "Kantonswechsel". Das gilt nicht nur, wenn kein Anspruch auf Kantonswechsel besteht, sondern auch dann, wenn sich der Ausländer auf einen solchen Anspruch berufen kann (vgl. Peter Uebersax, Einreise und Anwesenheit, in: Handbuch für die Anwaltspraxis zum Ausländerrecht, 2. Aufl. 2009, N. 7.324, S. 304; Thomas Häberli, Basler Kommentar zum Bundesgerichtsgesetz, 2008, N. 118 f. zu Art. 83 BGG; Alain Wurzburger, Commentaire de la LTF, 2009, N. 60 zu Art. 83 BGG). Der Gesetzgeber erkannte, dass die Schaffung zusätzlicher Rechtsansprüche - unter anderem auf Kantonswechsel gemäss Art. 37 AuG - zu neuen und längeren Beschwerdeverfahren führen könnte. Durch den Ausschluss der Beschwerde in öffentlich-rechtlichen Angelegenheiten in den in Art. 83 lit. c Ziff. 6 BGG genannten Bereichen wollte er die Verfahren beschleunigen und das Bundesgericht entlasten. Er erachtete einen Zugang zum Bundesgericht als verzichtbar, wenn der Aufenthalt in der Schweiz als solcher nicht in Frage gestellt ist (vgl. AB 2004 N 1163 Bundesrat Blocher sowie Nationalräte Steiner und Leuthard).
Damit ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen die Verweigerung eines Kantonswechsels neuerdings grundsätzlich ausgeschlossen, wiewohl sich der Ausländer auf ein Niederlassungsabkommen berufen kann. Entsprechend Art. 132 Abs. 1 BGG gilt der neue Art. 83 lit. c Ziff. 6 BGG für alle Beschwerdeverfahren, in denen der beim Bundesgericht angefochtene Entscheid - wie hier - nach dem 31. Dezember 2007 ergangen ist.
3. Das Bundesgericht kann die Eingabe indes als subsidiäre Verfassungsbeschwerde behandeln, sofern diesbezüglich sämtliche Sachurteilsvoraussetzungen erfüllt sind; die falsche Bezeichnung des Rechtsmittels schadet dem Beschwerdeführer nicht (vgl. Art. 113 und 119 BGG; BGE 134 II 379 E. 1.2 S. 382; <ref-ruling> E. 1.2 S. 302 f.; <ref-ruling> E. 3.1 S. 399). Soweit ein Ausländer keinen Anspruch auf Kantonswechsel hat, fehlt ihm die Legitimation, die Verweigerung der Zustimmung zu diesem Wechsel in materieller Hinsicht mit Verfassungsbeschwerde anzufechten; denn er hat kein rechtlich geschütztes Interesse an der Aufhebung des angefochtenen Entscheids (vgl. Art. 115 lit. b BGG; Urteil 2D_10/2009 vom 3. Februar 2009 E. 2.1 mit Hinweis auf <ref-ruling>). Anders verhält es sich, wenn der Beschwerdeführer - wie hier - einen Rechtsanspruch hat (Peter Uebersax, a.a.O., N. 7.329, S. 305); allerdings kann er mit der Verfassungsbeschwerde auch dann nur die Verletzung von verfassungsmässigen Rechten rügen (Art. 116 BGG). Dabei hat der Beschwerdeführer substantiiert darzulegen, inwiefern die erwähnten Rechte durch den angefochtenen Entscheid verletzt worden sein sollen (Art. 117 in Verbindung mit Art. 106 Abs. 2 und Art. 42 Abs. 2 BGG; vgl. auch <ref-ruling> E. 3 S. 351 f.; <ref-ruling> E. 1.4.2 S. 254; <ref-ruling> E. 3.2 S. 444). Hieran ändert nichts, dass die Vorinstanz in ihrer Rechtsmittelbelehrung fälschlicherweise allein auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten hinweist, zumal die Geltendmachung der Verletzung von verfassungsmässigen Rechten gemäss Art. 106 Abs. 2 BGG ohnehin bei allen Rechtsmitteln an das Bundesgericht einer qualifizierten Rügepflicht unterliegt und der Beschwerdeführer anwaltlich vertreten ist. Es besteht vorliegend kein Anlass, zusätzliche Rügemöglichkeiten entgegen dem klaren Wortlaut des Gesetzes einzuräumen.
4. Der Beschwerdeführer rügt einen Verstoss gegen seinen durch Art. 29 Abs. 2 BV geschützten Anspruch auf rechtliches Gehör. Die Vormundschaft über ihn werde inzwischen von einer Gemeinde des Kantons Solothurn wahrgenommen. Gemäss Art. 25 Abs. 2 ZGB habe eine bevormundete Person ihren Wohnsitz am Sitz der Vormundschaftsbehörde. Würde der Kantonswechsel nicht genehmigt, hätte er deshalb zivilrechtlich einen anderen Wohnsitz als fremdenpolizeilich. Darauf sei die Vorinstanz nicht eingegangen; damit habe sie ihre Begründungspflicht verletzt.
Wohl folgt aus dem Anspruch auf rechtliches Gehör unter anderem die Pflicht der Gerichte, ihre Entscheide zu begründen. Diese Pflicht verlangt indessen nicht, dass sich die Gerichte mit jeder tatbestandlichen Behauptung und jedem rechtlichen Einwand im Einzelnen auseinandersetzen; vielmehr können sie sich auf die ihrer Ansicht nach für den Entscheid wesentlichen Gesichtspunkte beschränken, so dass der Betroffene diesen gegebenenfalls sachgerecht anfechten kann. Diesen Anforderungen genügt der hier angefochtene Entscheid. Indem die Vorinstanz die Vormundschaftsbetreuung durch Behörden im Kanton Solothurn und Art. 25 Abs. 2 ZGB nicht weiter erörtert, bringt sie zumindest implizit zum Ausdruck, dass dies ihrer Ansicht nach nicht entscheidungsrelevant ist. Ob das zutrifft, bildet eine Frage der materiellen Beurteilung, die - wie erwähnt - bei der subsidiären Verfassungsbeschwerde auf die Prüfung der gerügten Verletzung von verfassungsmässigen Rechten beschränkt ist. Die Vorinstanz hat vorliegend jedenfalls nicht gegen ihre Begründungspflicht verstossen (vgl. allg. zur Begründungspflicht: <ref-ruling> E. 4.1 S. 88 mit Hinweisen; nicht publizierte E. 2 von <ref-ruling>, 2C_484/2008).
5. Der Beschwerdeführer beruft sich ausserdem auf Art. 13 Abs. 2 BV und macht eine Verletzung seiner Privatsphäre und des Grundrechts auf Datenschutz geltend: Ihm würden strafrechtliche Urteile vorgehalten, die den Behörden nur deshalb bekannt seien, weil sie "eine Art paralleles Strafregister angelegt" hätten. Dieses "Parallelstrafregister" sei ungesetzlich. Auch sei das Gleichbehandlungsgebot (Art. 8 BV) verletzt, weil der Beschwerdeführer anders behandelt werde, als wenn er gegen ihn verhängte Ordnungsbussen bezahlt hätte und die jeweiligen Übertretungen den Fremdenpolizeibehörden nicht bekannt geworden wären.
Es trifft zu, dass die Vorinstanzen dem Beschwerdeführer diverse Verstösse gegen gesetzliche Vorschriften vorwerfen. Es ist indessen fraglich, ob der Beschwerdeführer die soeben erwähnten Rügen vor Bundesgericht erheben kann, nachdem er sie schon bei der Vorinstanz hätte vorbringen können, dies aber offenbar unterliess (vgl. <ref-ruling> E. 2 S. 640; <ref-ruling> E. 1b S. 369 f.; Urteile 1C_312/2007 vom 31. März 2008 E. 3.3 und 1C_332/2008 vom 15. Dezember 2008 E. 1.5). Im Übrigen unterstützen sich die mit dem Vollzug des Rechts der Fremdenpolizei betrauten Behörden gegenseitig und erteilen die benötigten Auskünfte und gewähren auf Verlangen Einsicht in die Akten (Art. 97 Abs. 1 AuG). Gemäss Art. 97 Abs. 3 AuG in Verbindung mit Art. 82 der Verordnung vom 24. Oktober 2007 über Zulassung, Aufenthalt und Erwerbstätigkeit (VZAE; SR 142.201) melden die Polizei- und Gerichtsbehörden sowie die Strafuntersuchungsbehörden den kantonalen Ausländerbehörden unaufgefordert die Anhebung und die Einstellung von Strafuntersuchungen, Verhaftungen und Entlassungen sowie zivil- und strafrechtliche Urteile, soweit Ausländer davon betroffen sind. Zu den strafrechtlichen Urteilen sind auch Strafbefehle zu zählen. Für die Zeit vor Inkrafttreten des AuG gab es in den Kantonen Aargau und Solothurn bereits entsprechende Bestimmungen (vgl. gestützt auf Art. 25 Abs. 3 ANAG: § 14 der Solothurner Verordnung vom 22. März 1974 über Aufenthalt und Niederlassung der Ausländer; § 13 der Aargauer Vollziehungsverordnung vom 29. Dezember 1966 zum Bundesgesetz über Aufenthalt und Niederlassung der Ausländer). Zudem bestimmte Art. 15 der Vollziehungsverordnung des Bundesrates vom 1. März 1949 zum Bundesgesetz über Aufenthalt und Niederlassung der Ausländer (ANAV; AS 1949 I 228), dass die Polizei- und Gerichtsbehörden verpflichtet sind, der kantonalen Fremdenpolizei Mitteilung zu machen von Tatsachen, nach denen die Anwesenheit eines Ausländers als unerwünscht oder den fremdenpolizeilichen Vorschriften zuwiderlaufend erscheinen kann. Somit bestand bzw. besteht eine Rechtsgrundlage dafür, dass strafrechtliche Urteile und Strafbefehle in die Akten der Fremdenpolizei aufgenommen werden. Dieses Vorgehen ist daher nicht ungesetzlich. Da der Beschwerdeführer in diesem Zusammenhang keine anderen substantiierten Rügen geltend macht, erübrigt sich eine weitere Prüfung zu Art. 13 Abs. 2 BV.
Auch das Gleichbehandlungsgebot ist nicht verletzt. Ob die Fremdenpolizeibehörden von einigen Gesetzesverstössen des Beschwerdeführers bei Bezahlung der Ordnungsbussen nichts erfahren hätten, kann offen gelassen werden. Jedenfalls besteht insoweit ein sachlicher Grund zur unterschiedlichen Behandlung der Personen, die Ordnungsbussen begleichen, und derjenigen, die das unterlassen.
6. Im Übrigen legt der Beschwerdeführer nicht substantiiert dar (vgl. E. 3 hievor), dass das Niederlassungsabkommen und die bei einem Kantonswechsel zu beachtenden Grundsätze in Verletzung von Art. 8 EMRK oder des Willkürverbots und damit verfassungswidrig angewendet worden seien. Er erfüllt die Rüge- und Begründungserfordernisse in Bezug auf etwaige Verfassungsverletzungen insbesondere nicht, soweit er bloss eine falsche Anwendung von Bundesrecht geltend macht. Auf diese Vorbringen ist daher nicht weiter einzutreten.
7. Dem Dargelegten zufolge erweist sich die Beschwerde in öffentlich-rechtlichen Angelegenheiten als unzulässig. Als subsidiäre Verfassungsbeschwerde ist die Eingabe unbegründet, soweit auf sie eingetreten werden kann. Diesem Ausgang entsprechend hat der Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens zu tragen (Art. 65 und 66 Abs. 1 BGG). Der Antrag auf unentgeltliche Rechtspflege und Verbeiständung ist wegen Aussichtslosigkeit abzuweisen (vgl. Art. 64 Abs. 1 BGG). Mit Blick auf die Einkommens- und Vermögensverhältnisse des Beschwerdeführers werden aber reduzierte Gerichtskosten erhoben. Parteientschädigungen werden nicht geschuldet (vgl. Art. 68 BGG).

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird nicht eingetreten. Die subsidiäre Verfassungsbeschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Die Gerichtskosten von Fr. 500.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird dem Beschwerdeführer, dem Departement des Innern - Abteilung Ausländerfragen - sowie dem Verwaltungsgericht des Kantons Solothurn und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 4. Mai 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Merz