While it may seem reasonable to think that costs increase when you increase production, the transportation problem only considers the costs of moving things around. As a consequence, increasing production may provide opportunity to change how things are moved around, and that may help save costs.
For problems like this, is it often useful to think about an ideal situation. In the transportation problem, the ideal situation is where your supply is located as close to the demand as possible. That way, the costs of moving stuff around will be the lowest.
Unfortunately, we may have situations where there is a lot of supply at a location where there is not enough demand, and we have to move that supply to other locations. If demand would be increased at the location where there is excess supply, and the supply would be increased at the location where there was excess demand, you can get rid of some transportation costs, because the geographic imbalance of supply and demand is reduced. This is where the paradox comes from.
To give a pretty clear example: if the US produces 1 unit of apples, and Europe produces 2 units of apples, while the US has demand for 2 units of apples and Europe has only demand for 1 unit of apples, it is obvious you need to transport 1 unit of apples over the Atlantic Ocean. Now suppose the US increases it production to 2 units of apples. As a consequence the necessity to transport apples over the Atlantic disappears. The Europeans will be stuck with excess apples, and to overcome this issue they will probably lower the price, increasing demand of apples within Europe to 2 units of apples as well. Thus, by increasing supply and demand, we removed the geographic imbalance between supply and demand (all are 2), saving transportation costs compared to the previous situation where an imbalance existed.
Thus, the important thing to realize is that transportation costs are caused by a locational imbalance between supply and demand. Increasing supply and demand may give you an opportunity to reduce this imbalance and thus reduce transportation costs. The intuition that costs should increase when production is increased is valid, but this only applies to the production costs themselves and not how much we need to move around.