I will provide one solution which will be using Java and a simple [Java reloader][2] I recently introduced. This solution brings to the table up to 100-fold speed-up for large lists of dates.

###Preparation

I will borrow @Mike's functions to generate a random list of dates, from his code in [his recent question][1]


    RandomDateList[] := {
       RandomInteger[{1800, 2100}], 
       RandomInteger[{1, 12}], RandomInteger[{1, 28}], 
       RandomInteger[{0, 23}], RandomInteger[{0, 59}], 
       RandomInteger[{0, 59}]
    };

    RandomDates[n_] := Table[RandomDateList[], {n}]


###Implementation

1. Load the [Java reloader][2]

2. Compile the following class:

        JCompileLoad@
          "import java.util.*;
           public class DayOfWeekCalculator {
 	           public static int[] getDaysOfWeek(int[][] dateDataList){
 		          Calendar calendar = new GregorianCalendar();
 		          int[] result = new int[dateDataList.length];
 		          int ctr = 0;
 		          for(int[] date: dateDataList){						
 		    	     calendar.set(date[0],date[1],date[2]);
 		    	     result[ctr++]=calendar.get(Calendar.DAY_OF_WEEK);
 		          }
 		          return result;	
 	           }    
           }"

3. The actual function is then:

        Clear[dayOfWeek];
        dayOfWeek[dates_List] :=
           DayOfWeekCalculator`getDaysOfWeek@Transpose@
               {#[[All, 1]], #[[All, 2]] - 1, #[[All, 3]]} &@dates;

The input is a nested list of the type we construct randomly, which is a natural date format as it appears in Mathematica. I subtract 1 from month, to comply with the Java conventions.

###Use and benchmarks

    
    d=RandomDates[100000];

    dayOfWeek[d]//Short//AbsoluteTiming

    (*
       {0.1259765,{6,6,1,3,6,6,3,5,3,2,2,4,4,5,6,3,4,2,5,6,7,2,4,
         <<99954>>,2,2,3,1,1,6,5,7,6,7,5,1,6,3,7,4,6,4,5,7,4,1,3}}
    *)

    DayOfWeek/@d//Short//AbsoluteTiming

    (*
        {14.0732422,{Friday,Friday,Sunday,Tuesday,Friday, 
         <<99990>>,Thursday,Saturday,Wednesday,Sunday,Tuesday}}
    *)

There is a 100-fold speedup for this example. Note that there is a small constant overhead of calling Java, so the larger is your list of dates, the more you gain.

###Remarks

I think that this can be one of the "canonical" examples of a situation where the use of Java is more than appropriate. Generally, this happens when some of the following is true:

 - You have a large collection of Mathematica objects, which you want to process somehow.
 - The top-level overhead of explicit looping is (very) large, but the problem is not easily amenable to `Compile`
 - The functionality you seek for is readily available via Java libraries, or can be easily implemented using those.

Effective use of Java / JLink implies that loops are outsourced to Java. Only then the overhead of Java / JLink will not play a big role. Performing looping in Mathematica while invoking Java functions is likely to not be faster, and often be slower, than doing it all in Mathematica.

A big thanks goes to @Mike for spotting a bug in the reloader (which has been now fixed).


  [1]: https://mathematica.stackexchange.com/questions/7054/how-can-i-extend-bincounts-to-work-on-times-and-dates/
  [2]: https://mathematica.stackexchange.com/questions/6144/looking-for-longest-common-substring-solution/6376#6376