'Categories' and 'Labels' from Outlook do not transfer - you have all of your color-coded events in one calendar, which is what matters to the iPhone. You'd need to create multiple
calendars in Outlook. Your friends with iCal have multiple calendars, that's the source of the colors.
Actually picking colors is a separate issue - only with the most recent iTunes version do iCal colors sync properly (although they did so using MobileMe before that). I have no idea how you'd select colors for Outlook calendars, though - they may just be assigned in order, as they were for iCal before the last iTunes update.