The thread looks old and I do not know if you have already figured out a way or are still looking for one.
But here is what I would do. There is a free library called JFreeChart. You can use that to generate either a JPG or PNG file which you can then insert into excel file when you create it with Apache POI.
But the disadvantage with this method is that the data in the graph will not change dynamically when you change the data in the spreadsheet as is the case with Excel. Now that is something I cannot live with.
So I'm going to do some research now. I'm pretty sure that since the question has been asked there must be an addition of a feature in Apache POI or another elegant way of doing things. If I find any I will be sure to post my findings here.
---- UPDATE ----
In my research lasting for about an hour, I could only find one suitable library called SmartXLS (please google it, I could not post the link because i'm a newbie and the spam prevention mechanism kicked in) that is remotely close to what I would use. You can generate both the excel and the chart via a program. The website is very simple and I could not find any licensing information so I'm assuming it is free for personal and commercial use. I was able to download the library without any problem. I have not used it yet. Give it a shot and let us know how it works out.