The process shown below is for Opera running on OS X. The process may vary slightly on other operating systems, in particular mobile phones, Nintendo Wii, etc.
From the menu, open the "Tools" menu and then select "Delete Private Data":
Click on the "Details >>" button to display a list of options:
Ensure that the "Delete entire cache" option is selected (if you're just deleting the browser cache, de-select all the other options as shown below):