Yes this is just a term that is thrown around by management types but if you strip away the management language what he's saying is that he wants a department that is seen as using and embodying industry best practices in a way that others aspire to and is doing so to deliver great solutions people like.
(This last bit is important - if you're not actually delivering it doesn't matter how great everything else is and your manager won't be around long).
The complexity comes in two main ways:
1) Does he want this because he understands that it's the right way to develop software and that this is how you produce great products, or does he want it because he wants to be able to brag about it?
2) Will he accept the up front cost (time, money, credibility and risk) that comes with implementing best practice? It's fine to say "let's go agile" but he's laying his reputation on the line that it will improve things and is going to have to spend a lot of time selling it into the organisation. Almost always the benefits are long term, the costs are short term and that's the tough bit. Ultimately is he really serious about it?
In terms of what would it look like, well, that depends what you're doing but you need to be thinking in terms of what your development and project management processes are, what tools you're using, what kit people have and so on. The Joel Test is always a good place to start and in particular I'd want to see a really solid version control process, really good bug tracking and really good build processes.
I'd also look at whether agile methodologies are right for you (SCRUM in particular), to what extent automated testing could help (without starting a religious war there are differing beliefs about the point at which the complexity of the tests outweighs the benefits they provide) whether you've got the necessary tools and kit to do the job. Generally I'd suggest that you want tools to be on the leading but not bleeding edge. It's worth stressing that this isn't about having toys, it's about giving everyone in the team the tools to be as productive as possible for as much of the working day as possible. The most obvious example is bad PCs - is it really excellent to pay developers to watch a cursor while their project takes 5 minutes to build when they build it half a dozen times a day?
A few other things that are probably going to be visible in a centre of excellence: I'd suggest a software centre of excellence has likely got a pretty good training programme - maybe not formal courses but certainly book budgets, study time, mentoring and the like.
And I'd suggest that it's probably also doing a small amount (at least) of R&D. By that I don't mean completely blue sky stuff, but giving the developers room to try new things out and evaluate new tools and languages without the continual pressure of delivery to the client. That's how you move forward and stay good next year, the year after and so on.
How can you measure it? Ah, the age old question. Ultimately measuring software development is hard, if not impossible and measuring excellence in software development is similarly hard.
The only thing I can really suggest that I think would be useful that is widely adopted by a lot of companies is customer and staff satisfaction. It's an indirect measurement but my take would be that if you're not excellent, it's unlikely that you'd be getting really great levels of customer satisfaction and really great levels of staff satisfaction.