Did you restart the IDE after downloading NewSoftSerial?
Open a new sketch. Use Tools + Import Library..., and select NewSoftSerial. If that is not an option, you didn't install NewSoftSerial correctly (in the right place).
If that is the case, you need to either install it correctly, or tell us what OS and what version of the IDE you are using, so we can help you determine where the files go.