This is a good question. The ability to retrieve an Excel graph as an image with such a simple REST call is in my opinion the best feature of Excel Services that allows you to achieve an impressive result with a tiny amount of effort.
The chart image is generated by Excel Services itself (rather than the Excel Web App). The Excel web application is acting as a substitute for the Excel office client, so it is a proxy client running on the server and rendered in your browser, if you will. But when you are using the REST and web services it is talking directly to Excel Services. So it is running on any of your servers that is hosting Excel Services (as configured in Services on Server) with load balancing between these servers depending on your configuration. By default the load balancer will associate the same workbook with the same server every time, to facilitate caching.
As to when: it will be generated when the image is requested but subject to any caching that occurs in Excel services. I think you can rely on the image being up-to-date (i.e. cache will be invalidated if the underlying workbook is updated).
If you need to modify the image, you will need to do this by modifying the workbook itself to include the required functionality. If the built-in functions don't cut it, which sounds unlikely, you can develop custom user-defined functions in code.
There is an overview and more detailed configuration information on TechNet. There is also an Ignite video/lesson on Excel Services which is worth reviewing.