From what I understand of Canada's rate of interest on the debt, after Pierre Trudeau, it was around 17.4%, after Mulroney, it was around 7%, and after Harper it was around 5.2%.
Finding these figures are somewhat difficult, but to the point; what is setting these rates? Does any of it have to do with a country's credit rating?
The first thing to recognise is that an interest rate is a price because the interest rate tells you how much the borrower has to pay in return for receiving a loan.
The borrower would obviously like to pay as little as possible for the money s/he wants to borrow. But how little s/he can get away with paying depends upon how willing people are to lend their money. Here are some examples of how willingness to lend affects interest rates.
If the borrower already borrowed a lot of money and looks to be in danger of defaulting (i.e. not being able to pay everyone back) then lenders will be less willing to give him/her their money for fear for losing it. The borrower will therefore have to agree to pay a higher interest rate in order to induce people to be willing to lend.
If times are hard (i.e. in a recession) and money is short then it again becomes more likely that the borrower will be unable to repay their loan. Again, the borrower must be prepared to pay a higher interest rate to compensate lenders for this risk, otherwise they will refuse to lend.
People have lots of choices about where to put their money: government bonds (from many different governments), the stock market, savings accounts, pensions, real estate investment, corporate bonds, commodities, etc. The better is the return they get on alternative assets, the less willing a lender will be to give you their money. You then have to be prepared to pay more to induce lenders to give up all those lucrative alternatives. So borrowers will pay higher interest rates when returns in general are higher.
Not only the returns on other assets, but also their volatility matters. In times of uncertainty, assets like stocks or commodities are likely to be more volatile so that the return investors get on them becomes more risky. Since lending to certain actors (e.g. the government) is relatively safe by comparison, people will be more willing to lend money to these actors during uncertain times. Thus, the interest rate will tend to be lower during times of volatility and higher when alternative assets are experiencing relatively smooth growth.
If inflation is high then money loses its value quickly. I am going to be reluctant to give someone my money for five years if, by the time I get it back, it is worthless—I'd rather spend the money now while it's still worth something. Thus, to induce people to lend, the borrower will have to pay higher interest when inflation is higher.
Note that this reasoning applies to borrowing more generally (i.e. also by consumers or firms) as well as to government borrowing.
Interest rates are always determined by the certainty of the lender getting its money back. In the case of government bonds, that is: will the government default on its loan and will interest stay higher than inflation. The certainty of getting your money back is determined by a few factors: Debt to GDP ratio, Deficit, GDP growth and the history of a country paying back loans. For example if a country is known for defaulting on debt, they can only lend with high interest rates.
