Try this, it will give you a start.

SELECT DeptName

, [2001]

, [2002]

, [2003]

, [All]

FROM (

SELECT DeptName

, startyear = isnull(cast(year(StartDate) AS CHAR(4)), 'All')

, Cnt = Count(empid)

FROM StaffHistory

GROUP BY DeptName

, year(StartDate)

WITH rollup

) src

pivot(sum(Cnt) FOR startyear IN (

[2001]

, [2002]

, [2003]

, [All]

)) pvt

WHERE DeptName IS NOT NULL