2 B-tree indices OR 1 GiST index on tsrange -- which will perform better?
Timestamps with B-tree index
I suggest a third option: as long as your table holds two timestamp columns (which seem to be defined NOT NULL) I would use a single multicolumn index with opposed sort order (if no other considerations apply):
CREATE INDEX reservations_range_idx ON reservations using gist(starts_at, ends_at DESC);

More in these related answer:

Optimizing queries on a range of timestamps (two columns)
PostgreSQL index not used for query on range

As for the query, have a look at the SQL-standard operator OVERLAPS:
SELECT * FROM reservations
WHERE (starts_at, ends_at) OVERLAPS ('2014-01-01 00:00:00', '2014-01-03 00:00:00');

More in this related question on SO:

Find overlapping date ranges in PostgreSQL

Should be faster than two B-tree indices. Less disk space and cheaper to maintain. The burden on write operations is small
Range type with GiST index
With big tables, a GiST index on a range type is most probably faster, because it scales better. Storage on disk is considerably bigger and index maintenance a bit more expensive, though.
If you go that route, it would be more efficient to store your timestamp as range (tsrange or tstzrange) to begin with. A plain GiST index without the functional aspect is a bit faster.
CREATE TABLE reservation (
  reservation_id serial PRIMARY KEY
 ,span tsrange
 , ...
);

CREATE INDEX reservation_span_gist_idx on reservations USING GiST (span);

With the &amp;&amp; &quot;overlap&quot; operator you already displayed in the question:
SELECT *
FROM   reservation 
WHERE  span &amp;&amp; ('2014-01-01 00:00:00', '2014-01-03 00:00:00');

Also, you might be interested in an exclusion constraint to rule out overlaps by design, which implements a GiST index like the one above automatically. There is a code example in the manual. This related answer on SO has more details:

Preventing adjacent/overlapping entries with EXCLUDE in PostgreSQL