You can't do this through regular SOQL, as you can't group by a start and end date range.
If you want to accomplish this through a SOQL query on demand, you'll need an additional field in your custom object that contains the month (or maybe month/year, depending on whether you want Jan 2014 to be different to Jan 2013). While at first glance a formula field seems the best solution, you can't group by formula fields so you have to use a text field and populate this via workflow or a trigger. Once you have the field populated (I'm assuming its called MonYearStr__c) you can query back the totals and group by date and department, e.g.
List<AggregateResult> ars=[select count(id), MonYear__c,Department__c
from MyCustom__c group by MonYear__c, Department__c];
This will return a count of records for each unique Month/Year and department combination. You can then process the results and output your table.
If you don't want to add extra fields, you'll need to pull back all of the records and manually group them by date and department yourself - if there are a large number of records this might cause a problem with governor limits.