Option 1. Have your system accept that any login from Okta is valid and that if no corresponding user is found that a new user will be created. You will need to make sure that your assertion to the application contains all the fields that the application will need to create a new user. (Name, Email, etc. Whatever is needed.)
Using this option, User information will only be updated in the application when the user logs in.
Option 2. implement SCIM (http://www.simplecloud.info) on your application then enable provisioning from the Okta side. This option will keep users in synch with Okta data even if they never log in, but is more complicated and there is a Per User/Per Month charge from Okta on this.