My question is: Will I definately end up with orphaned users whenever I restore a database to another server?
No. Not necessarily. Orphaned users situation araises only if the login does not exist. If the logins exist, no orphansed users.
If I create the logins on the new server, will SQL make the link automatically between the DB Users and the logins?
Yes, if you create the logins with same SID.