I think this is really lame, but there is no native way to parse "complex" strings into dates with Apex at the moment (Jan'16). You will have to write your own substring utility method along the lines of:
String dateString = 'Thu Jan 14 2016 23:29:58 GMT+1100 (AEDT)';
String mon = dateString.subString(4,7);
String dat = dateString.subString(8,10);
String yea = dateString.subString(11,15);
String monNum = '1';
if(mon.equals('Feb')) monNum = '2';
if(mon.equals('Mar')) monNum = '3';
if(mon.equals('Apr')) monNum = '4';
if(mon.equals('May')) monNum = '5';
if(mon.equals('Jun')) monNum = '6';
if(mon.equals('Jul')) monNum = '7';
if(mon.equals('Aug')) monNum = '8';
if(mon.equals('Sep')) monNum = '9';
if(mon.equals('Oct')) monNum = '10';
if(mon.equals('Nov')) monNum = '11';
if(mon.equals('Dec')) monNum = '12';
theDate = Date.newInstance(integer.valueOf(yea),
integer.valueOf(monNum),
integer.valueOf(dat));
and also check your input will always give a 2 digit date value for day (ie the second is 02)... or the index won't line up for the year correctly. I have done this once or twice (through gritted teeth) in Salesforce.
The date.parse only turns the date string into a date/datetime if it matches the users Locale settings, you can't "provide" a format for it to interpret the dateTime out of (like Java etc.) - even though the date engine in Apex is literally using the SimpleDateFormat of Java.
Date.valueof()