Database indexing can reduce the CPU loading but I'd expect it to have more of an effect on disk usage, because it generally means that less information has to be retrieved in order to act on joins. I suppose you could see a knock-on effect when it comes to parsing the data.
However, you can't just randomly index a database and expect it to solve your problem. I assume that your host has provided evidence in the form of queries that are being ran that are using high CPU? If not then it would seem like it's a bit unfair to point the finger at the database.
On a simple level, indexing is only effective when you have a known set of queries that have been examined and it's been shown that by applying an index / indexes you can reduce the cost of the query plan.
You'd also have to taken into account what sort of traffic your site has. If you have a lot of write activity (comments, new posts, etc.) then adding indexes can add cost to the queries associated with those things. It's not a one-way street.