SoftwareSerial works fine on the Digispark except for the 16.5MHz clock speed. If you can wait a couple of days for @Digistump to release the next version of the digispark arduino app (or if you're on a mac,
use my beta build) you'll be able to select either the 16.0mhz or 8mhz digispark "board" from the Tools > Board menu. Both of these speeds compile fine with SoftwareSerial. I haven't tested it properly though and because of it's dependance on PCINT0, the timing maybe slightly off anyway. You might have more luck with lower speeds than higher ones.
These alernative clock speeds aren't compatible with using USB libraries like DigiUSB or DigiKeyboard, but SoftwareSerial conflicts with those by taking over the Pin Change Interrupt as well and it's nontrivial to resolve that issue.
The real solution would be for someone to spend the time rebuilding the table[] and XMIT_START_ADJUSTMENT = 6; for the 16.5mhz clock speed and possibly tweaking the other speed tables to take in to account the few instruction delay caused by the digispark bootloader on pcint0. Nicer solutions include using a timer to sample the pin instead of pinchange interrupts, which wouldn't conflict with usb libraries, but would mess with the frequency of PWM channels, or someone could implement HardwareSerial on digispark seeing as that seems to be what most people really want anyway. There's no reason the USI on the digispark can't implement hardware serial.
See also
this thread