I have a table that describes which software versions were installed on a machine at various times:
machine_id::integer, version::text, datefrom::timestamp, dateto::timestamp
In PostgreSQL 8.4 this can only be solved with triggers. The trigger will have to check on insert/update that no conflicting rows exist. Because transaction serializability doesn't implement predicate locking you'll have to do the necessary locking by yourself. To do that
SELECT FOR UPDATE the row in the machines table so that no other transaction could be concurrently inserting data that might conflict.
In PostgreSQL 9.0 there will be a better solution to this, called exclusion constraints (somewhat documented under CREATE TABLE). That will let you specify a constraint that date ranges must not overlap. Jeff Davis, the author of that feature has a two part write-up on this: part 1, part 2. Depesz also has some code examples describing the feature.