It's generally a losing strategy to try to find something to "replace sugar" i.e. which is sweet like sugar and yet which doesn't have any of the nutritional properties of sugar. That should make you suspicious of agave nectar and artificial sweeteners (having learnt through millions of years of evolution, the body isn't easy to fool!). That said there's some evidence to think that honey is just a (relatively less harmful) sugar substitute. This clashes with all my prima facie intuitionsbut Matthew has collected some suggestive evidence. That said, despite honey's status as less-destructive-than-refined-sugar substitute I would strongly suspect that it is still far from an optimal food. As a rule, I'd say that if you're eating enough 'sugar' that it's necessary to find a "substitute," then you're probably eating too much even with the substitute. Conversely, if you're only lightly sweetening some heavy cream for dessert every once in a while, then I wouldn't worry about the sugar too much. There's no justification for thinking some "natural" replacement will allow you to eat lots of sugary-stuff without health downsides.
Tabbed miracle berries work well... I'll have one before a bit of really dark bitter chocolate. That's a bit exotic isn't it? It's not actually sweet, but it makes anything you eat that's bitter or sour taste sweet so you could eat lemons or swig vinegar straight and it's quite good :P It is also great with cranberries as well, they're sweetened up loads and taste like a really ripe cranberry flavoured blueberry. I've always really wanted to try it with bitter melon, but I haven't found one yet :)
For "desserts", I eat a small amount of carrots or berries, a bit of large flaked, unsweetened coconut (I like Bob's Red Mill), some sliced jicama sprinkled with ground cinnamon, or a tablespoon or two of almond butter. What I've found about this lifestyle is that when you cut the highly processed and sweetened foods, the natural sugars of fruits and vegetables comes out immensely.
I've never tried stevia but I think for me it would be too much of a crutch for sweet things.
I try to avoid sugar whatsoever. If I really want to add something and it doesn't make sense to add some naturally sweet thing, like berries, I would use very little sweetener. I know it's a processed, chemical "food", but I use it so seldom, that it's hardly a problem. I don't need to sweeten my coffee (heavy cream is sweet enough), and the rest of the food I like is on the salty side (like meats). Once in a while I feel like baking something with coconut flower or so, then I would add something. The good thing is, now very little sweet taste goes a long way. I don't think I would be able to enjoy old style cookie anymore!