If you had the icloud backup feature turned on and had a backup made (from the lost device), then just get a new device and restore the backup. Without a backup in icloud or iTunes, your data is lost.
Go to Settings>General>Reset and tap Erase All Content and Settings. This will erase your device. Then you will go through the setup screens again as you did when your device was new, and when given the option, select Restore from iCloud Backup.
This link gives another overview of backup and restore: