I think Hadron was right that the sales guy put your contacts on the SIM card, which no one should do anymore.
You need to get your contacts saved to your Google account (aka Gmail). To do it follow these steps. This is a kinda general guide, they might be somewhat different on your phone. The user manual will also explain this. Also, your phone may have a 'Convert SIM contacts to Google contacts' function built-in. If so, you can use it to skip 1-4 below.
1. Open the Contacts app. Tap Menu (3 dots in the corner).
2. Select Import/Export contacts. It may offer some choices. You want to select Export from SIM or similar terminology.
3. It may offer a choice of file types. For this job, choose CSV. Export to file.
4. From the Contacts menu, select import and import as Google contacts. Do the import of the CSV file you created.
5. In the main phone Settings > Accounts > Google > tap the account name and make sure Sync contacts is checked.
From now on, as long as when you add a contact, be sure it's saved as a Google contact and it went will be automatically uploaded for backup and easy restoration when you change phones.