I believe pictures taken on your iPhone (Camera Roll) can be deleted from the iPhone itself by clicking on the little garbage can when viewing the picture. However pictures put on your phone through a manual sync (Photo Library) must be done through iTunes.
If you want to delete more than one photo at a time from the "Camera Roll" I find the best way to do it is to use the Image Capture program. Even if you have synced your iPhoto pics with your Mac via iPhoto previously (it seems that you can not delete pics by selecting the "delete from camera after sync" in IPhoto), use the "delete from camera after downloading" function in Image Capture and it does work. You will probably want to delete the photos downloaded via Image Capture (sittingin the photos album) if you already have them from the iPhoto sync.