Would just stealing an apple from a market stall justify crucifixion?
Would they have stolen something more valuable like a horse?
Would they be repeat offenders?
Were there any general standards of punishment that applied empire-wide, or was the punishment entirely determined by the whim of the local governor?
What was the lowest ranking government official who could order a crucifixion?
I'm paging /u/KiwiHellenist for this, because "thieves" is a translation from Latin, which itself is an imperfect translation of the original Greek. The Greek text reads "leistai", and that is not quite "thieves". A more adequate translation would be "outlaws", "rebels", and such. Leistai is more in the semantic field of sedition than that of theft.
Edit: Fixed a couple of typos