When is a DNA sequence a gene?
We can devide algorithms for protein-coding genes in eukaryotes in two main categories:
 


Extrinsic, these algorithms rely on the comparison with external data sources,  such as comparing genomes
Intrinsic, I suggest you are more interested in this one when you acctualy want to predict gene coding regions on your own (If I'm wrong I will further explain extrinsic methods). The intristic methods are based on ab into predictions. 



I will continue on Intrinsic methods, so what can we use to identify coding genes in the sequence. Ofcourse we need to know the charasticts of those coding regions:

Most of the time we see CpG Islands(regions of a higher than expected occurrence of CpG dinucleotides over a patricular region).


  About 70% of human promoters have a high CpG content (Wiki)


Those CpG islands are important for the regulation of gene expresion.

the basics of a coding sequence are the promotor, introns and exons.
you are probably familiar with the fact that a mRNA has to be spliced in order to cut the introns (non coding regions) out, this is done by the splicesome wich recognizes special sites where it can cut, So you can search for these sites in your DNA sequence.  I will summarize some points about the coding regions here: 


CpG Island near the promotor 
splice sites for splicesomes
Start and stop codons (I hope you are familiar with these)


There are more things to consider but I would to suggest to look at the algorithms of these programs: GENSCAN, FgeneSH, GeneMark, Xpound and to read this atricle which is about identifying the protein-coding regions