I think you might have Safari assigned to all Workspaces. If you have Lion, Right click (or Ctrl click) on the Safari Dock icon, Choose "Options" and under "Assign To" choose "None". If you have Snow Leopard, check System Preferences => Expose & Spaces, Under Spaces, check Application Assignment.