Solution 1:

private Random gen = new Random();
DateTime RandomDay()
{
    DateTime start = new DateTime(1995, 1, 1);
    int range = (DateTime.Today - start).Days;           
    return start.AddDays(gen.Next(range));
}

For better performance if this will be called repeatedly, create the start and gen (and maybe even range) variables outside of the function.

Solution 2:

This is in slight response to Joel's comment about making a slighly more optimized version. Instead of returning a random date directly, why not return a generator function which can be called repeatedly to create a random date.

Func<DateTime> RandomDayFunc()
{
    DateTime start = new DateTime(1995, 1, 1); 
    Random gen = new Random(); 
    int range = ((TimeSpan)(DateTime.Today - start)).Days; 
    return () => start.AddDays(gen.Next(range));
}

Solution 3:

I have taken @Joel Coehoorn answer and made the changes he adviced - put the variable out of the method and put all in class. Plus now the time is random too. Here is the result.

class RandomDateTime
{
    DateTime start;
    Random gen;
    int range;

    public RandomDateTime()
    {
        start = new DateTime(1995, 1, 1);
        gen = new Random();
        range = (DateTime.Today - start).Days;
    }

    public DateTime Next()
    {
        return start.AddDays(gen.Next(range)).AddHours(gen.Next(0,24)).AddMinutes(gen.Next(0,60)).AddSeconds(gen.Next(0,60));
    }
}

And example how to use to write 100 random DateTimes to console:

RandomDateTime date = new RandomDateTime();
for (int i = 0; i < 100; i++)
{
    Console.WriteLine(date.Next());
}