Admin - Catalog - Categories/Products - New Category

at the bottom, where it says 'category image' - click Browse to find the image on your computer.