Hallo,
eigentlich ist es doch egal, wie tief es liegt - erst wenn es an die Oberfläche kommt (oder die Oberfläche zu ihm herunterkommt) findet man es

Ich nehme an, wenn wir hier über versteinerte Hölzer reden, dann sind verkieselte H. gemeint...
Das Vorkommen verkieselter Hölzer ist extrem faziesabhängig, viel stärker als bei Fossilien mobiler Organismen. Zu einem Wald bzw. lockeren Baumbestand (in der Erdgeschichte nicht immer so häufig wie heutzutage) muss das passende Einbettungsmilieu (See, Altarm eines Flusses) in der Nähe kommen, und dort müssen dann auch noch die richtigen Bedingungen für Verkieselung herrschen (Sediment, in dem Silikatverbindungen in mobilisierbarer Form vorliegen), sonst gibt es höchstens Kohle.
Ein reiner ("reifer") Sandstein besteht zwar per Definition überwiegend aus Quarz, dieser liegt jedoch in kaum löslicher Form vor. Dagegen können feldspatreiche ("unreife") Sandsteine oder Vulkanite reichlich Kieselsäure aus der Verwitterung von Feldspäten, Amphibolen etc. bereitstellen, besonders in warmem und feuchtem oder zumindest periodisch feuchtem Klima.
Ein Beispiel aus eigener Erfahrung: Ich habe bei zig Gelegenheiten Aufschlüsse im heimischen Stubensandstein abgeklappert, weil dieser einerseits die perfekten Bedingungen für Verkieselung bietet und andererseits zur Entstehungszeit von Nadelbaumgruppen bewachsen war - es hätte sich also was finden lassen müssen, und reichliche Funde sind auch durchaus bekannt. Bis auf ein paar dünn gesäte Kleinstücke aber nada... Eines Tages stand ich dann in einem Aufschluss, der einen Altarm des Deltasystems erschloss, und siehe da, Stämme steckten kreuz und quer in der Wand, weil sie sich in einer Stillwasserzone angereichert hatten

Der größte Fund aus dem Aufschluss ließ sich grade noch so von 2 Personen anpacken, ein perfekt erhaltenes Stammsegment mit fast 100 kg! Der Fundhorizont lag ca. 4 m unter der Bodenoberfläche, aber das ist dabei völlig irrelevant.
Am praktischsten ist es, wie Gucknetso es beschreibt: Da, wo ohnehin schon reichlich fossiles Holz auf dem Acker liegt, stehen die Chancen nicht schlecht, in geringer Tiefe noch mehr zu finden. Und wenn es viele kleine Holzfragmente gibt, stammen sie höchstwahrscheinlich von größeren Stämmen, die beim Pflügen zerbrochen werden.
Wenn Du Dir Fundorte in Dir geologisch unbekanntem Terrain selbst erarbeiten willst/musst und keinen lokalen Kenner der Materie als Führer bzw. eine konkrete Fundortangabe hast, musst Du logisch vorgehen: Über den Ausstrich potenziell holzführender Schichten gibt Dir eine geologische Karte Auskunft (es dürfen keine marinen Schichten sein); Kenntnis über die Entstehungsweise und -zeit sowie Ablagerungsraum der Schichten hilft, das Potenzial für Verkieselung oder überhaupt das Vorkommen von Bäumen bzw. Baumartigen richtig einzuschätzen. Und danach: viel Geduld!
Gruß,
Triassammler