The core concept of the 5th edition warlock is that he has very few spell slots. Yes, they regenerate on a short rest. But up to including level 10 you can only cast 2 spells between those short rests, while other spellcasters have 15 spell slots at level 10. Even if your group takes two short rests every day, your warlock still will cast a lot less spells than a wizard or cleric. To play a warlock well, you need to use your few spells for effects that last for some time, and which support your fighting style for the turns in which you don't cast spells. For a regular warlock that might be casting Eldritch Blast cantrips, while for a hexblade that might be attacking with a weapon.

Good warlock spells are for example Hex at level 1, or Darkness at level 2. Hex adds damage to each of your attacks. Darkness, combined with the eldritch invocation Devil's Sight, creates a zone through which only you can see. Obviously you need to be careful not to blind your own group with it, but the radius of the darkness zone is only 15 feet, so that is doable. Bad warlock spells are for example Arms of Hadar or Hellish Rebuke. Because you don't make an attack roll, they don't count as "attacks", so the damage of Hex isn't added. And with so few spell slots, using a spell just to deal a bit of instant damage is kind of a waste. One exception would be a spell like Scorching Ray (if you chose the Fiend patron), where the damage of Hex is added to each of the three attacks you make.

But even if you can make your warlock efficient, how do you make him otherwise interesting as a personality? The key here is obviously the very special relation that the warlock has with his patron. The patron isn't necessarily evil; but even if he is, the warlock doesn't have to be evil too. Unlike a cleric and his god, the warlock is far more likely to be at odds with the goals of his patron. The warlock might be like the character Faust, not fundamentally evil but ambitious, and willing to compromise morality for the sake of power.

For my warlock, I made all the choices that affected gameplay first, and created the backstory afterwards. I'm not saying that this is how you have to do it, it depends on your style, and the style of the campaign you are playing in. I play with people who enjoy tactical combat, so making a character that with a very interesting story, but who isn't very useful in combat, wouldn't have worked. Warlocks chose their patron already at level 1, and with me being a human hexblade with the polearm feat, my patron obviously needed to be a sentient magic polearm. So for me the backstory needed to explain how my character ended up making a pact with a sentient weapon, and what that weapon was. One important thing to consider with any backstory is that it needs to be sufficiently open, as you will want the DM to be able to build it into his campaign.

The patron I created was the Halberd of St. Matthew (because I found a picture of a saint with a halberd on the internet). But I made St. Matthew an evil saint of the god Bane, the Faerunian god of tyrannical oppression, terror, and hate. And I decided that rather than an evil saint wielding the halberd for tyrannical oppression in the name of Bane, it was rather the evil halberd that used that cleric of Bane. Having chosen the "criminal (smuggler)" background, I decided that a contact of mine had hired me to smuggle him and something he stole out of Waterdeep. Before the rendezvous my character heard that the Halberd of St. Matthew had been stolen from the temple of Bane in Waterdeep. Then I found my contact dead, with the halberd splitting his skull. Trying to make his body disappear before the priests of Bane found me, my character touched the halberd. And the halberd spoke to him, promised him power, and basically forced him to return the halberd to the temple. (Because, hey, no DM will allow you to keep a powerful artifact you invented yourself in your backstory at level 1).

So this gives me all the backstory elements for my character that I need, and that my DM needs. The character is not evil, but he is an opportunist and didn't turn down the magical power the unholy halberd promised him. Now the halberd will try to further corrupt him towards tyranny, terror, and hate. At the same time my character is also on the run from the priests of Bane who could reasonably be after somebody involved in the heist of one of their artefacts, even if it was returned. All this gives the DM a number of possible hooks, both positive (the Halberd of St. Matthew promised to help him find other powerful halberds to wield) and negative (with the priests of Bane possibly being after him). And for me the story not only gives an explanation of how my character became a hexblade, but also creates interesting possibilities for ambiguity, with the morals of the patron not being the same as the morals of the character. How much evil will the character be forced to do in order to gain more warlock powers? If the campaign goes on for longer, and DM cooperates: Will the character at some point be powerful enough to wield the Halberd of St. Matthew? And if yes, how does he get it back from the temple of Bane?

At level 1, my character just presents himself as a criminal on the run from a heist gone bad. He is willing to join a group of adventurers on their way into the wilderness in order to lay low. But he also feels that he will have to use his newfound warlock powers in order to grow them. I'll see how it goes from there.