This question has indeed been asked before...by just about every one of us! Almost every new photographer I know (myself included) got this kind of unhappy introduction to the subject of aspect ratio, so don't feel alone.
Aspect ratio is the ratio of the width of a photo to the height. A digital photo can be expanded or contracted without cropping only if the aspect ratio is the same. For example a photo with an aspect ration of 2:3 can be printed in a 4x6, 8x12, or 20x30 size without having to be cropped. Go try to find an 8x12 frame, however, and you may well be in for a challenge. Standard frame sizes are 4x6, 5x7, and 8x10, all of which have different aspect ratios.
You are right that a border is how to get it to work. To avoid this problem in the future, try to frame your shot with enough room around the subject so that the photo can be cropped in several ways without losing important detail. You can then crop to fit whatever frame size you want to print.