Trying to make your service stateless is a worthy goal. Whether having order IDs in query strings is "safe" depends on a lot of things, though. The main things you may need to worry about are:
- users altering their order ID
- order IDs "leaking" to third-parties
- order IDs being predicted by third-parties
I say "may" because which things you actually need to worry about depend on details of your system. What are the consequences of these things happening? Depending on the details of your system these may be harmless or they may be very serious.
The easiest problem to solve is the "leaking" issue. Use HTTPS. This not only prevents "eavesdroppers", but also prevents leaks due to proxy logs and Referer headers.
The prediction issue can be solved by encrypting (yes, in addition to HTTPS -- we don't want the end-user decrypting this either) the order ID that appears in the query string. That way someone can't just inc/decrement the query string to find another order ID. (This also prevents users from easily figuring out the total number of orders in your system, which may be desirable.)
You can solve the issue of the user altering their order ID by either recording who an order ID belongs to when it is first allocated, or by including a secure signature of the (user, orderid) pair as a query parameter. Then a user can only change their order ID to one they already own, which at least prevents them from screwing around with someone else's orders. If you do this, you probably don't need to do the encryption of order IDs, unless you want to prevent users from knowing how many orders exist.
These are just some ideas. Which of these apply to your system depend on the factors I mentioned earlier.