1) If your friend has already linked his account to Facebook, linking your account to Facebook will automatically add your friend as well.
2) Alternatively, in the main town, tap on the bottom right "Friends List" icon.
a) Tap "Add Friend" in the bottom right corner.
b) Input your friend's ID. This is the 9 character ID found beside his/her hero portrait on the Friends List.