clips and straps can be tricky at first, heres a description of the basic steps:

http://www.63xc.com/gregg/101_7.htm

bikes (and fixed gears are no exception) can be full of maddening little tricks to learn, but once you get them down they'll feel like second nature.

edit: i absolutely HATE running shoes for bike riding. too thick, too squishy. indoor soccer shoes are popular because they have thin soles and a lot of sensitivity on the top up by the toe (where the clip sits is the same area as where you kick a soccer ball).