There are a few potential issues here.
We don't know the make and/or model of the laptop, and thus we don't know how old it is.
We don't know the environmental conditions you use the laptop in. Warm and/or humid conditions make a large difference as opposed to an air conditioned room.
In general, switching over from Windows to Linux often poses a very specific problem; namely that of processor throttling. Relatively modern computers, regardless of whether they use an Intel processor or an AMD processors, tend to have processor related drivers installed that will throttle the processor when there isn't a demand. That means at idle or when you are performing light tasks (and you are using Windows with all the proper drivers installed) the CPU will actually run at a slower speed... thus generating less heat. You don't see this with Linux in general, because by default you won't have any drivers like that installed... depending on which kernel is being used. It wasn't until 2011 and kernel version 2.6.18 that AMD's Cool and Quiet was able to be used (using the powernow-k8 driver). So this is one potential issue. Your CPU might be a relatively modern one, running at full speed all the time generating more heat than it would normally.
As to the first two points I mentioned, if the laptop is more than a year old, and it is used in an average home environment, you could be looking at dust blocking the heat sink fins. Like this...
Feel free to search Google for "laptop heatsink dust" if you'd like to see more images. The point is that the cooling fan will draw normal room dust and debris up through the fan itself and blow it against the leading edges of the heat sink. As some of that material catches, it works like a screen, catching even more dust and debris until you can get a layer of material not unlike a piece of felt. If you need a more concrete analogy, the heat sink can act like a DRYER LINT TRAP... if you've ever cleaned one of those out. As that material backs up, the air cannot flow through the heat sink properly, and the laptop will get hotter and hotter since it cannot shed heat properly. Unfortunately, most laptops have to be taken apart to be able to separate the fan from the heat sink assembly to be able to clean between them. So... if we knew how old the laptop was, and the make and model of the laptop, we could estimate the likely hood that your issue is simply a need to clean the unit.
Check your BIOS. If your laptop has an AMD processor, make sure Cool N Quiet is enabled. Make sure you are using a version of Linux that is newer than 2011. Make sure that your laptop's cooling channel is clean and free of dust.