How to create a border around an image?

Thanks, this was a helpful and easy to follow explanation. 

How to use the Appearance panel to add stroke step-by step (as described by @Andrey Kozyakov above:

1. Select the image
2. In the Appearance panel, Click the Add stroke button
   
3. Select the stroke. For now the stroke is not yet visible
   You can drag the stroke under/below the Image if you don't wan the stroke to overlap the image later.
   
4. While the stroke is selected, click the fx button at the bottom of the panel
   Select Convert to Shape -> Rectangle
   
5. Click Preview.
   Now the stroke/border is visible.
   Set to Relative.
   Set the Extra Width and Extra Height to zero if you want the border to be exactly the size of the image
   
6. Click OK. Now you can set the border to different styles.
   1. You can set the stroke to different thickness, dashed, symmetrical, etc... in the Stroke Panel
      
   2. Or behind the image
      
   3. You can add more strokes
      
   4. Or you can add more effects on a stroke
      

Also it is possible to create a border without adding new objects but using effects in Appearance panel.

In this way we need to use 'Add new stroke' button in Appearance panel. Then select this Stroke in the panel and click on 'Fx' button there, find in the list and add Convert to shape > Rectangle effect. In effect options just use 'Relative' size instead of 'absolute' values. 
I'm not sure that this way is easier   But it also works

Hi Will,

You can create separate rectangular shape and use it as a mask and border for the image.
Create rectangular shape, be sure it is above the image. Select the shape and the image, and use Object > Clipping Mask > Make command (Cmd+7 / Ctrl+7)

Then you have to select the mask (rectangular frame) only using 'Direct Selection' and choose color and weight  in the Stroke panel.