I think the Waughs will be replaced quickly and easily. There is a bag of talent within the oldies like Lehmann, Maher, Love, Bevan, Blewett etc. and then with young guns of Katich, Hussey and Watson... batting is strong in Australian cricket.
I think MacGill will probably slot into the team for a while after Warnie (I'm guessing the end of the '03-'04 Aussie summer??) if he's in form, otherwise there is some spinning talent in Hauritz and even in young guys like Cameron White (I think it's Cameron, anyway). Spin bowlers won't be a problem either.
However, Mighty McGrath will be a tough one to replace. The opening combination of Gillespie and Lee doesn't look anywhere near as strong and reliable. Also, there have been few bowlers (apart from Bichel) who have been knocking on the selectors' doors consistently in the past few years. There is no where near the fast-bowling depth in Australia as there is in the batting.
However, I will say that this is a reasonably pessimistic view. Many people were saying how Australian cricket wouldn't be as strong when Boarder retired, or McDermott retired or Taylor retired. And yet, in post-Boarder and post-McDermott times, Australian cricket has never been stronger. All I'm saying is, perhaps Gillespie will go on to take 400 wickets, and Hauritz will cement his place in the side and take 500+ wickets and these two will become the best bowlers in Australian history....
(yeah.....)
Mark Waugh, Steve Waugh, Shane Warne and Glenn McGrath are all good, but there will be better players for Australia than all of these guys... it's just a matter of time.