This should come through natural progression. However, you need to make sure that when you meet a new companion that you request that they come with you and this dismisses your current companion for it to count towards the trophy.
Below is a link to the current list from the Fallout 4 wiki page of companion and location. Obviously when you meet them be nice and indicate that you would like them to follow you.
http://fallout.wikia.com/wiki/Fallout_4_companions