The biggest problem of the Arab factions is that Arabia is nearly devoid of supplies. The region itself has only one supply centre based in Gerrha and it will need to be seized in order to increase the might of your armies. This supply centre is based very near to the Sabaeans' starting position so the Sabaeans may be able to expand fairly quickly and early once this is obtained. Ideal targets of expansion include the lands up north or northeast, but these tend to be held by the Seleucids, so a lot of diplomacy is required for Nabtaea or Saba to survive their first few turns.
The early AI player for Nabataea often offers vassal rights to the human Egypt player; this offer should be accepted at all costs.