まず場所の選定が必要です。

昔、内モンゴル自治区の砂漠の中に住んでいたことがあります（とはいっても数カ月の話ですが、オルドス盆地の北部です）。ゴビ砂漠と言われるところは、私自身どこからどこまでを言うのかはっきりしませんが、イメージ的には西はタクラマカン砂漠の西はずれから、内モンゴル自治区の続く中国東北3省の近くの砂漠地帯まで東西数千kmに及ぶと思います。
どこに行かれたいのかによって、またその目的、どうした手段で「横断」したいのか、によって費用も日数もいろいろ変わってきます。バスの路線のあるようなところを中国人と一緒にバスに揺られていくのか、四輪駆動車をチャーターして独自に行くのか、ラクダと徒歩で横断したいのか、等々ということです。
まずは、いろんな資料から、的を絞るのが先決だと思います。