Is SoftwareSerial left out for the ATTiny85/84?
Short answer - no. It's not left out, on the contrary. 

But before addressing to the compiler error you mentioned, a small clarification:


  I downloaded the hardware from https://code.google.com/p/arduino-tiny/


The link you provided is not hardware, but software called the ATtiny core files. It contains the necessary files that will help you compile and upload code from Arduino IDE to the ATtiny (even when using ArduinoISP as programmer). 

The SoftwareSerial is a library that comes with the Arduino IDE zip/installation. If you have downloaded the latest version of Arduino IDE from the Arduino Website, you should be able to find the SoftwareSerial library files located at:

[Path to Arduino installation folder]\libraries\SoftwareSerial


Example for SoftwareSerial library files you should expect to find there are SoftwareSerial.cpp and SoftwareSerial.h.


  fatal error: SoftwareSerial.h: No such file or directory


The compiler error you receive seems to imply that the compiler cannot find the header file (SoftwareSerial.h) for SoftwareSerial library. This indeed seems quite odd, since this library does not require any special installation, and as mentioned, is part of the libraries that are built into the Arduino IDE installation.

So, to mitigate this, I would recommend that you will:


Make sure the library folder exists in the location mentioned above
If it doesn't, then you should probably re-download the Arduino IDE installation, and after that install the ATtiny core files as per the instructions (important!). Installation instructions are located in the README file inside the ATTiny core zip file 
(tiny\avr\README).
If it does exist, and you still get this compiler error, then you must have a corrupted installation (perhaps the compiler include folders is messed up). I would still recommend following the re-installation as mentioned in the previous bullet. 
Make sure that you can find the ATtiny 85 in the board list, at Tools->Board and that it is selected.
Another angle that might shed more light on this error, would be to turn on the verbose output for the compiler (you can do it in the Arduino IDE, by choosing File->Preferences-> "Show verbose output during" and checking "compilation"). Verbose output can help you track down any compiler command line errors, like missing include folders. 
Last but not least, if the SoftwareSerial folder exist, you could use the Arduino IDE to check if the IDE can identify its existance, by going to Sketch->Import Library, and looking for SoftwareSerial. If it's not there, then the folder is not located properly under the 'libraries', verify the path as mentioned above (did you move it?)


Finally, when you will be able to compile your code, try using the SoftwareSerial example that comes with the library to check it. Note that it is not going to work 'out-of-the-box' as with the Arduino Uno; The ATtiny does not have the same FTDI hardware for communicating directly with USB, so for sending and receiving serial messages using the ATtiny you will have to either use the Arduino Uno as a proxy (using the Uno's pins 0 &amp; 1) or to use dedicated USB to Serial hardware similar to this one. 


  Switching the board to UNO makes the problem go away


As a side note, switching to the Uno will make most ATtiny problems 'go away' since the Uno is much more equipped than ATtiny85/4, both on the MCU level and on the breakout board level, which you get with the Uno (and which you don't get when working directly with a chip like ATtiny). Also, most of the code base out there is targeting the Uno and not ATTiny.
So if you are doing your first steps with the ATtiny, be prepared that many things that 'just worked' with the Uno will require extra/different code before they could work with the ATtiny (and some won't work at all).

You can use my simple Analog to Serial code :

/*
Takes an input on the AtTiny85 from the VERY TRICKY analogue input pin 2 (as labeled in HLT tutorial)
 and outputs these with Software serial to the arduino uno, or Duemillanove
 Hookup
 ATTINY85 pin 3 -&gt; Arduino Uno pin 0
 ATTINY85 pin 4 -&gt; Arduino Uno pin 1

http://www.instructables.com/id/Easy-ATTiny-Serial-Communication-with-Tiny-AVR-Pro/
 */


#include &lt;SoftwareSerial.h&gt;
// Definitions
#define rxPin 4
#define txPin 3
SoftwareSerial mySerial(rxPin, txPin);
int sensorPin = 7; //ACTUALLY PIN LABELED AS "2" on the HLT tutorial
int sensorVal = -1;


// the setup routine runs once when you press reset:
void setup() {
  pinMode(sensorPin, INPUT);
  mySerial.begin(9600);
analogWrite(0,1); // This is kind a heart beat to show the ATTINY is "alive"
}

// the loop routine runs over and over asensorpingain forever:
void loop() {
  sensorVal = analogRead(sensorPin);
  mySerial.print("Input Val: ");
  mySerial.print(sensorVal);
  mySerial.println();
}