How do you take a complex image and create an outline around it?

Like Monica asked, is that a pixel or vector image?

If it's a pixel based image you could try opening it in Photoshop and creating a work path via a selection of the image. First you would need to expand the canvas to make room for the outline around the image. Then use the Color Range command to create a selection (Select>Color Range). Once a selection is created use the Select>Modify>Expand command to grow the selection around the image. You might have to experiment with pixel values to get the outline thickness desired. Finally, open the Paths palette and select "Make Work Path..." from the drop down menu. That will vectorize the selection. Double click the resulting path to convert it from being a temporary work path to a saved and named path. Then you can go to File>Export>Paths to Illustrator to create an Adobe Illustrator file from that path. I'll often create an additional work path the size of the canvas to include with the other path so it can be used for registration purposes to line up with the image when imported into other graphics applications.

Like all auto-tracing methods, the Create Work Path trick can sometimes yield messy results or results not as clean or accurate as desired. Sometimes I'll just manually trace the path I want using the Pen tool.

If the image is vector based then I would consider using the Offset Path command in Illustrator.

Is that a pixel or a vector image?