San Andreas jest bardziej zagadkową grą od poprzednich serii gier Grand Theft Auto z powodu większej ilości niespodzianek (easter eggs) i tworzonych przez graczy domysłach. Krótko po wydaniu gry, na forach internetowych pojawiły się doniesienia o istnieniu w grze Wielkiej Stopy oraz opublikowano kilka zrzutów z gry. Okazały się jednak one potem albo sfałszowane albo były rezultatem złej identyfikacji obiektu. Wielu graczy jednak broniło swoich racji, twierdząc, że Wielka Stopa nie była jedynie ich wymysłem.

W grze na pustyni znajduje się "strefa zamknięta" nazwana Strefą 69, co jest oczywistą parodią rzeczywistej Strefy 51. Stanowiło to podwalinę dla spekulacji dotyczących niezidentyfikowanych obiektów latających i kosmitów. Duże mapy stanu San Andreas dostępne w domu Mike'a Toreno, w podziemnej Strefie 69 oraz w barze nazwanym "Lil Probe Inn" ("Pod Małą Sondą") mają pozaznaczane markerem różne miejsca w całym stanie. Gracze początkowo myśleli, że mapa jest kluczem do odgadnięcia zagadki UFO, jednakże Rockstar powiedział, że te mapy nie mają nic wspólnego z UFO, gdyż tych obiektów w grze po prostu nie ma.

Innym dowodem na występowanie istot pozaziemskich w grze miała być misja "Stowaway". Po wejściu na pokład samolotu, bohaterowie niezależni (bazowani na popularnych "teoriach" spiskowych nt. UFO) zaczynają atakować gracza, wykrzykując jednocześnie dużą liczbę różnych tekstów wyrażających ich pogardę dla "gorszej" rasy ludzkiej ("Carbon-based buffoon" ["Węglowy śmieć"], "You evolved from shrews!" ["Rozwinęliście się z odpadów!"] i tym podobne).

Inną pogłoską są tzw. samochody-widmo. Samochody-widmo to pojazdy, które pokazują się w tych samych miejscach, chwilowo przemieszczając się oraz mające uszkodzenia, których nie można naprawić w żadnych warsztatach. Jeden z nich pojawia się w strefie Back o Beyond gdzie toczy się na dół bez kierowcy za kółkiem. Ciekawostką jest fakt, że jedna lokacja pojawiania się samochodu-widmo zbiega się z zaznaczeniem na mapie Torena. Pewien gracz nazwany "NullZilla" wyszedł poprzedniemu twierdzeniu naprzeciw twierdząc, że ten niby samochód-widmo jest tak naprawdę normalnym samochodem, a stacza się tylko dlatego, że jego punkt spawnujący jest na pochyłej nawierzchni, więc nie jest to nic innego jak mały błąd programistów.

Różne samoloty okazjonalnie rozbijają się na terenie całego stanu San Andreas, po czym po chwili znikają. Jeden z takich samolotów rozbija się koło znaku VINEWOOD. Inny od południowej strony góry Mount Chillad.

Parę tygodni po ogłoszeniu zagadek i stworzeniu paru zespołów sprawdzających te zagadki, na różnych forach internetowych zaczęły pojawiać się posty z adresu "Mouthoff@rockstargames.com". Wielu kwestionowało autentyczność tych wiadomości, ale po dodatkowym sprawdzeniu prawdopodobne było, że posty te rzeczywiście pochodzą od pracownika Rockstar Games.

Po pierwszym poście, na ten adres zaczęło spływać mnóstwo listów od fanów, więc uruchomiona została automatyczna odpowiedź. Początkowo zwroty do nadawców zawierały mało informacji więc fani zaczęli podejrzewać, że nie jest to pracownik firmy Rockstar. Niedługo po tych podejrzeniach właściciel adresu stworzył nowy list powrotny, w którym były umieszczone kolejne zagadki oraz zaprzeczenie niektórych istniejących. Niektórzy spekulowali, że są to po prostu plotki producenta mające na celu stworzenie większego zainteresowania grą.

Najważniejszą informacją tego listu było zaprzeczenie istnienia w grze Wielkiej Stopy. Autor listu poinformował także, że jednak coś w lasach się znajduje.

Listy zawierały również wzmianki o lądowaniu obcych na pustyni w grze. Mimo że było to często powtarzane przez fanów, nie znaleziono żadnych dowodów potwierdzających te doniesienia. Jednakże na niebie San Andreas często pojawiają się latające dyski. Wielu twierdzi, że to właśnie są niezidentyfikowane obiekty, dodane przez Rockstar do gry. Inni wytaczają przeciwko tej teorii argument, że Rockstar użył tego samego stylu do animacji lotnictwa w Grand Theft Auto: Vice City (jasne światła, smugi dymu, itp.) ale zapomniał o zmianie sprite'ów. Z tego wniosku można by wysunąć kolejny: jest to uproszczony model samolotu stworzony po to, aby nie zajmować dużo miejsca w pamięci operacyjnej konsoli/komputera. Rockstar natomiast nic nie powiedział na temat tych "znaków na niebie", więc jego intencje są wciąż niejasne. Należy również zauważyć że pewne smugi światła widoczne na niebie nawet w biały dzień to często choć nie zawsze po prostu znaki pomocnicze w odnalezieniu tzw. zdjęć które po prostu widać dopiero gdy spojrzymy na nie przez obiektyw aparatu, dzieje się tak np. w przypadku lokacji boiska sportowego w San Fierro, gdzie nad boiskiem wyraźnie widać smugę światła lecz, gdy spojrzymy na nią przez wspomniany już aparat okazuje sie ona zdjęciem które należy wykonać aby odblokować nagrody tak jak w przypadku zamalowywania tagów lub zbierania podków czy ostryg. Po jego wykonaniu smuga znika.

Niektórzy fani znaleźli w teksturach gry różne zwierzęta, np. sarny czy dinozaury. Powinno to podtrzymać jedną z pierwszych pogłosek, tą na temat występowania w grze zwierząt. Dość dziwnym zachowaniem fanów było, mimo zaprzeczenia przez Rockstar istnienia Wielkiej Stopy, wznowienie twierdzeń na jej temat, mówiąc przy tym, że być może zostali oni po prostu wprowadzeni w błąd. Jest pewne, że w grze występują zwierzęta morskie – można znaleźć delfina, żółwia, meduzy i różnego rodzaju ryby. Jednakże nigdy nie udowodniono, że w grze istnieją zwierzęta żyjące na lądzie.

Rockstar Games również, jak zawsze, odwoływało się m.in. do konkurencyjnych gier w postaci różnych easter eggów. Jednym z takich przykładów są billboardy w Los Santos, na których jest prezentowana okładka stylizowana na okładkę gry True Crime: Streets of LA odnosząc się do niej jakoby nadawała się jedynie do śmieci. Większość easter eggów znajdujących się w San Fierro jest związana z inspirowanym na Golden Gate Bridge moście dostępnym w grze oraz serii gier i filmów Resident Evil.

Jak wszystkie trójwymiarowe części serii gier Grand Theft Auto, również San Andreas cechuje "podziemne miasto", tutaj nazywane "Oblivion" (z ang. "Zapomnienie") lub Matrix lub "Blue Hell" (z ang. "Niebieskie Piekło"). Część nazwy Hell (z ang. Piekło) najpewniej wzięła się z faktu, że gdy gracz nie weźmie ze sobą do tych lokacji spadochronu, może po prostu zginąć. Gdy bohater znajdzie się w niewłaściwym miejscu, może po prostu zacząć zapadać się pod ziemię, a gdy już kompletnie się zapadnie, pojawia się wtedy wysoko nad miastem, więc spadając baz spadochronu na pewno zginie. W "Niebieskim Piekle" znajduje się wiele ciekawych obiektów, m.in. niekompletny model Liberty City z Grand Theft Auto III. Właśnie ten częściowy model miasta Liberty City jest używany podczas misji "St. Mark's Bistro", podczas której CJ wraca do Liberty City, aby wykonać robotę dla Salvatore'a Leone.

Wielu przechodniów w grze ma skłonności do popełniania dziwnych samobójstw. Niektórzy twierdzą, że może być to błąd w oskryptowaniu szukania ścieżek ruchu dla nich i nie jest to żaden easter egg. Na przykład w Los Santos Inlet fotograf po zrobieniu zdjęcia miasta Los Santos idzie skoczyć do wody, aby się utopić. Właśnie z tego powodu inni gracze mówią, że jest to nawiązanie do stworzonej przez firmę DMA Design (tak nazywała się firma Rockstar North przed przejęciem jej przez Rockstar Games) gry Lemmings. Dziwnym przypadkiem jest też to, że w wielkim wieżowcu w Los Santos jest paru ludzi. Oni sobie skaczą z dachu (trzeba podejśc nie za blisko, aby Gracza nie "zauważyli" (wtedy oni przestają skakać) i nie za daleko, aby ich widzieć (można sobie przybliżyć obraz aparatem). Tak samo dzieje się w Las Venturas w pobliżu największego kasyna ulokowanego na północy miasta.

Budynek korporacji "ZomboTech" w San Fierro jest odwołaniem do firmy Umbrella Corporation z serii gier Resident Evil. Z tego powodu pojawiły się niepotwierdzone pogłoski o zombie, pojawiających się w nocy w San Fierro. Inna popularna, acz niepotwierdzona pogłoska dotyczy zdjęć z cmentarzy, na których miałyby się pojawiać różne duchy, w tym duch matki CJ-a. Pomimo, że nie znaleziono żadnych dowodów na istnienie w grze duchów, lecz widać "ich" działalność. Na przykład cmentarz w Los Santos w nocy zostaje obrysowany graffiti. Owe graffiti ("Grove Street 4 Life" – "Grove Street na zawsze") znika, gdy słońce pojawia się na horyzoncie.

W styczniu 2005 roku w magazynie Electronic Gaming Monthly był zawarty wywiad z CEO Rockstara, Terrym Donovanem, który zaprzeczył istnieniu Wielkiej Stopy: "W grze nie ma Wielkiej Stopy, tak, jak nie ma jej w rzeczywistości" ("There is no Bigfoot, just like in real life"). Donovan powiedział również, że w grze nie występuje duch matki CJ-a oraz wielu innym pogłoskom dotyczących gry. W następnym wydaniu EGM ukazał się list czytelnika, w którym był zrzut ekranu z mistyczną kreaturą występującą na terenach wiejskich. Magazyn nazwał tą kreaturę Yeti zamiast Wielką Stopą.

Podążając za stroną internetową Programu Epsilon i podobnymi "przeciekami", gracze zaczęli szukać miejsca spotkań kultu Epsilon. Epsilon wydaje się być parodią Kościoła scjentologicznego. Gracze znaleźli przechodniów, którzy rozmawiają o Kifflom ("bóstwie" Programu Epsilon). Nie potwierdzono jeszcze, czy te dialogi mają jakiś dodatkowy cel poza stworzeniem spójnego świata gry. Jedna z dziewczyn głównego bohatera, Katie, pielęgniarka znająca sztuki walki, również odwołuje się do tej grupy społecznej, mówiąc: "Ten cały Epsilon mnie wkurza" ("Those Epsilon nut-jobs freak me out"). Wyznawcy Epsilon cechują różne, sprzeczne z nauką, opinie, jak na przykład "Świat ma 157 lat" ("The World is 157 years old"), popieranie znanych osobistości, a (Jezz Torrent powiedział, że Grupa pomogła wyjść mu z uzależnienia narkotykami. O Grupie Epsilon można również usłyszeć w radiu WCTR podczas programu Entertaining America z Lazlowem, który przeprowadza wywiad w założycielem Programu, Chrisem Fromage, który również odwołuje się do Kiffloma.

Jednym z najbardziej rozpoznawalnych easter eggów w całej grze jest umieszczone na południowym szczycie mostu Gant Bridge w San Fierro (bazowanym na Golden Gate Bridge z San Francisco) graffiti, na którym jest napisane: "Tu nie ma żadnych niespodzianek. Odejdź" ("There are no Easter Eggs up here. Go away."). Jest ona nawiązaniem do trzeciej części serii Grand Theft Auto, gdzie na szczycie mostu między wyspami znajdował się inny Easter Egg.