The key difference between the two is that the Profile is the users base set of permissions and all users are assigned to one.
A Permission set is just a way to give a user or a set of users extended permissions without granting them to the entire group of users with a certain Profile.