what payment gateway are you using?
Most likely you are using a Remote checkout like paypal Payments standard.
With a remote checkout system, the order info needs to be stored in the database before the user is sent to the gateway site to process the transaction.
you should have a status column in your order table that uses the default value of pending.
depending on the payment gateway you are using, you may need to login to your account to view the status of the order, then update it is your data base manually.
or with paypal standard, you can set up an IPN script to update the status automatically for you.
see the following page for more details: